给定一个大小为 $K$ 的环 $R$。

环是一类包含两种运算（乘法 $\otimes$ 和加法 $\oplus$）的代数系统，满足

• $\forall a,b,c\in R,(a\oplus b)\oplus c=a\oplus (b\oplus c)$（加法结合律）
• $\forall a,b\in R,a\oplus b=b\oplus a$（加法交换律）
• $\forall a\in R,a\oplus 0=a$（加法单位元）
• $\forall a\in R,\exists (-a)\in R,a\oplus (-a)=0$（加法逆元）
• $\forall a,b,c\in R,(a\otimes b)\otimes c=a\otimes(b\otimes c)$（乘法结合律）
• $\forall a\in R,1\otimes a=a\otimes 1=a$（乘法单位元）
• $\forall a,b,c\in R,a\otimes(b\oplus c)=(a\otimes b)\oplus (a\otimes c),(b\oplus c)\otimes a=(b\otimes a)\oplus (c\otimes a)$（分配律）

考虑所有 $N$ 维向量 $\boldsymbol u=(u_1,u_2,…,u_N)$（这里的每 $\boldsymbol u$ 一维都是 $R$ 中的元素），定义向量加法 $$ \boldsymbol{u}+\boldsymbol{v}=(u_1\oplus v_1,u_2\oplus v_2,\dots,u_N\oplus v_N) $$ 以及数量乘法 $$ a\cdot \boldsymbol{u}=(a\otimes u_1,a\otimes u_2,\dots,a\otimes u_N) $$ （这里 $a∈R$）。

对于一个向量集合 $S=\{\boldsymbol{s_1},\boldsymbol{s_2},\dots,\boldsymbol{s_n}\}$，我们称其能够表示 $\boldsymbol u$ 当且仅当。$\exists a_1,a_2,\dots,a_n\in R,\sum_{i=1}^{n}a_i\boldsymbol{s_i}=\boldsymbol{u}$

称一个 $N$ 维向量集合 $S$ 是一个完全表示，当且仅当它能够表示所有 $N$ 维向量。

求所有 $N$ 维完全表示的大小的 $M$ 次方和对 $164511353$（一个质数）取模的结果。

输入格式

第一行输入三个数 $N,K,M$。

第二行输入一个数 $tp$。

我们认为 $R$ 中的每个元素唯一对应 $[0,K)$ 中的一个整数。特别地，保证加法单位元对应 $0$，乘法单位元对应 $1$。

如果 $tp=1$，则 $∀i,j∈R$，$i⊕j=(i+j)\bmod K$，$i\otimes j=(i\times j)\bmod K$。

如果 $tp=2$，接下来输入 $2K$ 行每行 $K$ 个数。

对于前 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊕j$。

对于后 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i⊗j$。

输出格式

输出一行一个数，表示答案对 $164511353$ 取模的结果。

样例 1

输入

2 2 3
2
0 1
1 0
0 0
0 1

输出

196

解释

全体完全表示为：$\{(0,0)(0,1)(1,0)\}$，$\{(0,0)(0,1)(1,1)\}$，$\{(0,0)(1,0)(1,1)\}$，$\{(0,0)(0,1)(1,0)(1,1)\}$，$\{(0,1)(1,0)\}$，$\{(0,1)(1,1)\}$，$\{(1,0)(1,1)\}$，$\{(0,1)(1,0)(1,1)\}$，答案为 $3\times 2^3+4\times 3^3+1\times 4^3=196$

样例 2

输入

2 3 3
2
0 1 2
1 2 0
2 0 1
0 0 0
0 1 2
0 2 1

输出

61995

解释

该样例输入等价于

2 3 3
1

样例 3

输入

2 4 1
2
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

输出

524132

限制与约定

对于所有数据，$1≤N≤100000,2≤K≤100000,0≤M≤1000,∀i,j∈R,i⊕j,i⊗j∈[0,K)$，保证输入是一个合法的环。

时间限制：1s

空间限制：1GB