P5293 [HNOI2019] White Rabbit’s Dance

HNOI2019 day2t2

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

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]$.

The output file name is dance.out. Output $k$ lines in order, each containing one number: the answer modulo $p$.

### 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