Given a ring $R$ of size $K$.

A ring is an algebraic system containing two operations (multiplication $\otimes$ and addition $\oplus$) that satisfies:

• $\forall a,b,c\in R,(a\oplus b)\oplus c=a\oplus (b\oplus c)$ (associativity of addition)
• $\forall a,b\in R,a\oplus b=b\oplus a$ (commutativity of addition)
• $\forall a\in R,a\oplus 0=a$ (additive identity)
• $\forall a\in R,\exists (-a)\in R,a\oplus (-a)=0$ (additive inverse)
• $\forall a,b,c\in R,(a\otimes b)\otimes c=a\otimes(b\otimes c)$ (associativity of multiplication)
• $\forall a\in R,1\otimes a=a\otimes 1=a$ (multiplicative identity)
• $\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)$ (distributive laws)

Consider all $N$-dimensional vectors $\boldsymbol u=(u_1,u_2,…,u_N)$ (where each component of $\boldsymbol u$ is an element of $R$), and define vector addition as $$ \boldsymbol{u}+\boldsymbol{v}=(u_1\oplus v_1,u_2\oplus v_2,\dots,u_N\oplus v_N) $$ and scalar multiplication as $$ a\cdot \boldsymbol{u}=(a\otimes u_1,a\otimes u_2,\dots,a\otimes u_N) $$ (where $a\in R$).

For a set of vectors $S=\{\boldsymbol{s_1},\boldsymbol{s_2},\dots,\boldsymbol{s_n}\}$, we say it can represent $\boldsymbol u$ if and only if $\exists a_1,a_2,\dots,a_n\in R$ such that $\sum_{i=1}^{n}a_i\boldsymbol{s_i}=\boldsymbol{u}$.

A set of $N$-dimensional vectors $S$ is called a complete representation if and only if it can represent all $N$-dimensional vectors.

Calculate the sum of the $M$-th powers of the sizes of all complete representations of $N$-dimensional vectors, modulo $164511353$ (a prime number).

Input

The first line contains three integers $N, K, M$.

The second line contains an integer $tp$.

We assume that each element in $R$ corresponds uniquely to an integer in $[0, K)$. Specifically, it is guaranteed that the additive identity corresponds to $0$ and the multiplicative identity corresponds to $1$.

If $tp=1$, then $\forall i,j\in R$, $i\oplus j=(i+j)\bmod K$ and $i\otimes j=(i\times j)\bmod K$.

If $tp=2$, the next $2K$ lines each contain $K$ integers.

For the first $K$ lines, the $(j+1)$-th element of the $(i+1)$-th line represents $i\oplus j$.

For the next $K$ lines, the $(j+1)$-th element of the $(i+1)$-th line represents $i\otimes j$.

Output

Output a single integer representing the answer modulo $164511353$.

Examples

Input 1

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

Output 1

196

Note 1

The complete representations are: $\{(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)\}$. The answer is $3\times 2^3+4\times 3^3+1\times 4^3=196$.

Input 2

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

Output 2

61995

Note 2

This input is equivalent to:

2 3 3
1

Input 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

Output 3

524132

Constraints

For all test cases, $1\le N\le 100000, 2\le K\le 100000, 0\le M\le 1000, \forall i,j\in R, i\oplus j, i\otimes j\in [0, K)$, and it is guaranteed that the input forms a valid ring.