Problem Background

HNOI2019 day2t2

Problem Description

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 graph 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]$ different edges from $(u_1, v_1)$ to $(u_2, v_2)$. If $u_1 \ge u_2$, there are no edges.

The White Rabbit will perform a dance on this graph. Initially, the White Rabbit is at vertex $(0, x)$.

The White Rabbit will take several steps. In each step, the White Rabbit will move from the current vertex to the next vertex along any outgoing edge. The White Rabbit can stop dancing at any time (it can also end without taking any steps). It must stop when it reaches a vertex with the first coordinate $L$ because there are no outgoing edges from such a vertex.

Suppose the White Rabbit stops after taking $m$ steps. The dance will be recorded as a sequence where the $i$-th element is the edge it took in the $i$-th step.

The problem is: 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$) exist such that $m \mod k = t$ and the White Rabbit stops at a vertex with the second coordinate $y$.

Two dances are considered different if their lengths ($m$) are different or there exists a step where they took different edges.

The output should be modulo $p$.

Input Format

The input file is named dance.in.

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

The next $n$ lines, each containing $n$ integers separated by spaces, represent the matrix $w$ where the $i$-th row and $j$-th column denote $w[i][j]$.

Output Format

The output file is named dance.out.

Output $k$ lines, each containing a number representing the answer modulo $p$.

Sample Input and Output

Sample Input #1

2 2 3 1 1 998244353
2 1
1 0

Sample Output #1

16
18

Sample Input #2

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

Sample Output #2

506551216
528858062
469849094
818871911

Notes

Sample Explanation 1

For $t = 0$:
1. Path length is $0$, there is $1$ solution.
2. Path length is $2$, there are six types of paths:
- $(0,1)\to (1,1)\to (2,1)$ with $w(1,1) \times w(1,1) = 4$ paths;
- $(0,1)\to (1,1)\to (3,1)$ with $w(1,1) \times w(1,1) = 4$ paths;
- $(0,1)\to (2,1)\to (3,1)$ with $w(1,1) \times w(1,1) = 4$ paths;
- $(0,1)\to (1,2)\to (2,1)$ with $w(1,2) \times w(2,1) = 1$ path;
- $(0,1)\to (1,2)\to (3,1)$ with $w(1,2) \times w(2,1) = 1$ path;
- $(0,1)\to (2,2)\to (3,1)$ with $w(1,2) \times w(2,1) = 1$ path;

The answer is $1 + 4 + 4 + 4 + 1 + 1 + 1 = 16$.

For $t = 1$:
1. Path length is $1$, there are three types of paths:
- $(0,1)\to (1,1)$ with $w(1,1) = 2$ paths;
- $(0,1)\to (2,1)$ with $w(1,1) = 2$ paths;
- $(0,1)\to (3,1)$ with $w(1,1) = 2$ paths;
2. Path length is $3$, there are three types of paths:
- $(0,1)\to (1,1)\to (2,1)\to (3,1)$ with $w(1,1) \times w(1,1) \times w(1,1) = 8$ paths;
- $(0,1)\to (1,1)\to (2,2)\to (3,1)$ with $w(1,1) \times w(1,2) \times w(2,1) = 2$ paths;
- $(0,1)\to (1,2)\to (2,1)\to (3,1)$ with $w(1,2) \times w(2,1) \times w(1,1) = 2$ paths;

The answer is $2 + 2 + 2 + 8 + 2 + 2 = 18$.

Data Range

For all data, $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$.

For each test case, special restrictions are as follows:
- Test points $1,2$: $L \le 10^5$;
- Test point $3$: $n = 1, w(1,1) = 1$, the largest prime factor of $k$ is $2$;
- Test point $4$: $n = 1$, 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$.

见题面 Input 部分

见题面 Output 部分