Description

There is a directed graph with $(L+1)\times n$ vertices. Each vertex is represented by an ordered pair $(u,v)$, where $(0\le u\le L,1\le v\le n)$.

This graph is not a simple graph. For any two vertices $(u_1,v_1)(u_2,v_2)$, if $u_1<u_2$, then there are exactly $w[v_1][v_2]$ different edges from $(u_1,v_1)$ to $(u_2,v_2)$. If $u_1\ge u_2$, then there is no edge.

The white rabbit will perform a dance on this graph. Initially, it is at vertex $(0,x)$.

The white rabbit will make several jumps. In each jump, it moves from the current vertex to the next vertex along any outgoing edge. It can stop at any time (it may also stop immediately without making any jump). When it reaches a vertex whose first coordinate is $L$, it must stop, because that vertex has no outgoing edges.

Suppose the rabbit stops after making $m$ jumps. It will record this dance as a sequence, whose $i$-th element is the edge it took in its $i$-th jump.

Now, given positive integers $k$ and $y$ ($1\le y\le n$), for each $t$ ($0\le t<k$), find how many dances (with length $m$) satisfy $m \bmod k=t$, and the rabbit finally stops at a vertex whose second coordinate is $y$.

Two dances are considered different if their lengths ($m$) are different, or there exists some step at which the edges they take are different.

Output the results modulo $p$.

Input Format

The input file name is dance.in.

The first line contains five integers $n,k,L,x,y,p$ separated by spaces.

Then follow $n$ lines, each containing $n$ integers separated by spaces. The $j$-th number in the $i$-th line denotes $w[i][j]$.

Output Format

The output file name is dance.out.

Output $k$ lines in order, each containing one number: the answer modulo $p$.

2 2 3 1 1 998244353
2 1
1 0

16
18

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

506551216
528858062
469849094
818871911

Hint

Sample Explanation 1

$t=0$:

1. Path length is $0$, and the number of ways is $1$.
2. Path length is $2$. There are six types of paths:
   • $(0,1)\to (1,1)\to (2,1)$: this path has $w(1,1)\times w(1,1)=4$ ways;
   • $(0,1)\to (1,1)\to (3,1)$: this path has $w(1,1)\times w(1,1)=4$ ways;
   • $(0,1)\to (2,1)\to (3,1)$: this path has $w(1,1)\times w(1,1)=4$ ways;
   • $(0,1)\to (1,2)\to (2,1)$: this path has $w(1,2)\times w(2,1)=1$ way;
   • $(0,1)\to (1,2)\to (3,1)$: this path has $w(1,2)\times w(2,1)=1$ way;
   • $(0,1)\to (2,2)\to (3,1)$: this path has $w(1,2)\times w(2,1)=1$ way;

So the answer is $1+4+4+4+1+1+1=16$.

$t=1$:

1. Path length is $1$. There are three types of paths:
   • $(0,1)\to (1,1)$: this path has $w(1,1)=2$ ways;
   • $(0,1)\to (2,1)$: this path has $w(1,1)=2$ ways;
   • $(0,1)\to (3,1)$: this path has $w(1,1)=2$ ways;
2. Path length is $3$. There are three types of paths:
   • $(0,1)\to (1,1)\to (2,1)\to (3,1)$: this path has $w(1,1)\times w(1,1)\times w(1,1)=8$ ways;
   • $(0,1)\to (1,1)\to (2,2)\to (3,1)$: this path has $w(1,1)\times w(1,2)\times w(2,1)=2$ ways;
   • $(0,1)\to (1,2)\to (2,1)\to (3,1)$: this path has $w(1,2)\times w(2,1)\times w(1,1)=2$ ways;

So the answer is $2+2+2+8+2+2=18$.

Constraints

For all testdata, $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$, and $1\le L\le 10^8$.

For each test point, the special constraints are as follows:

• Test points $1,2$: $L\le 10^5$;
• Test point $3$: $n=1,w(1,1)=1$, and the largest prime factor of $k$ is $2$;
• Test point $4$: $n=1$, and the largest prime factor of $k$ is $2$;
• Test point $5$: $n=1,w(1,1)=1$;
• Test point $6$: $n=1$;
• Test points $7,8$: the largest prime factor of $k$ is $2$.

Translated by ChatGPT 5