There is a directed graph with $(L+1) \times n$ vertices. Each vertex is represented by a tuple $(u, v)$ where $0 \le u \le L$ and $1 \le v \le n$. This is not a simple graph; for any two vertices $(u_1, v_1)$ and $(u_2, v_2)$, if $u_1 < u_2$, there are $w[v_1][v_2]$ distinct edges from $(u_1, v_1)$ to $(u_2, v_2)$. If $u_1 \ge u_2$, there are no edges.

A white rabbit performs a dance on this graph. The rabbit starts at vertex $(0, x)$. The rabbit makes several steps. In each step, the rabbit moves from the current vertex to a next vertex along any of the outgoing edges. The rabbit can stop at any time (it can also stop without making any moves). When the rabbit reaches a vertex where the first coordinate is $L$, it must stop because there are no outgoing edges from such vertices.

Suppose the rabbit stops after $m$ steps. The rabbit records this dance as a sequence, where the $i$-th element of the sequence is the edge traversed in the $i$-th step.

Given positive integers $k$ and $y$ ($1 \le y \le n$), for each $t$ ($0 \le t < k$), calculate the number of dances (assuming length $m$) such that $m \equiv t \pmod k$ and the rabbit ends at a vertex with the second coordinate $y$. Two dances are considered different if their lengths $m$ are different or if there exists at least one step where the edges traversed are different. Output the results modulo $p$.

Input

The first line contains five space-separated integers $n, k, L, x, y, p$. The next $n$ lines each contain $n$ space-separated integers, where the $j$-th number in the $i$-th line represents $w[i][j]$.

Output

Output $k$ lines, each containing one integer representing the answer modulo $p$.

Constraints

• $p$ is a prime number, $10^8 < p < 2^{30}$
• $1 \le n \le 3$
• $1 \le x \le n$
• $1 \le y \le n$
• $0 \le w[i][j] < p$
• $1 \le k \le 65536$, $k$ is a divisor of $p-1$
• $1 \le L \le 10^8$

Data Range

• Test cases 1, 2: $L \le 100000$
• Test case 3: $n=1, w[1][1]=1$, the largest prime factor of $k$ is 2
• Test case 4: $n=1$, the largest prime factor of $k$ is 2
• Test case 5: $n=1, w[1][1]=1$
• Test case 6: $n=1$
• Test cases 7, 8: The largest prime factor of $k$ is 2

Examples

Input 1

2 2 3 1 1 998244353
2 1
1 0

Output 1

16
18

Note 1

For $t=0$: 1. Path length 0, 1 way. 2. Path length 2, 6 types of paths: $(0,1) \to (1,1) \to (2,1)$ has $w[1][1] \times w[1][1] = 4$ paths $(0,1) \to (1,1) \to (3,1)$ has $w[1][1] \times w[1][1] = 4$ paths $(0,1) \to (2,1) \to (3,1)$ has $w[1][1] \times w[1][1] = 4$ paths $(0,1) \to (1,2) \to (2,1)$ has $w[1][2] \times w[2][1] = 1$ path $(0,1) \to (1,2) \to (3,1)$ has $w[1][2] \times w[2][1] = 1$ path $(0,1) \to (2,2) \to (3,1)$ has $w[1][2] \times w[2][1] = 1$ path Total: $1+4+4+4+1+1+1 = 16$.

For $t=1$: 1. Path length 1, 3 types of paths: $(0,1) \to (1,1)$ has $w[1][1] = 2$ paths $(0,1) \to (2,1)$ has $w[1][1] = 2$ paths $(0,1) \to (3,1)$ has $w[1][1] = 2$ paths 2. Path length 3, 3 types of paths: $(0,1) \to (1,1) \to (2,1) \to (3,1)$ has $w[1][1] \times w[1][1] \times w[1][1] = 8$ paths $(0,1) \to (1,1) \to (2,2) \to (3,1)$ has $w[1][1] \times w[1][2] \times w[2][1] = 2$ paths $(0,1) \to (1,2) \to (2,1) \to (3,1)$ has $w[1][2] \times w[2][1] \times w[1][1] = 2$ paths Total: $2+2+2+8+2+2 = 18$.

Input 2

3 4 100 1 3 998244353
1 1 1
1 1 1
1 1 1

Output 2

506551216
528858062
469849094
818871911