题目背景

HNOI2019 day2t2

题目描述

有一张顶点数为 $(L+1)\times n$ 的有向图。这张图的每个顶点由一个二元组$(u,v)$表示$(0\le u\le L,1\le v\le n)$。 这张图不是简单图，对于任意两个顶点 $(u_1,v_1)(u_2,v_2)$，如果 $u_1<u_2$，则从 $(u_1,v_1)$ 到 $(u_2,v_2)$ 一共有 $w[v_1][v_2]$ 条不同的边，如果 $u_1\ge u_2$ 则没有边。

白兔将在这张图上上演一支舞曲。白兔初始时位于该有向图的顶点 $(0,x)$。

白兔将会跳若干步。每一步，白兔会从当前顶点沿任意一条出边跳到下一个顶点。白兔可以在任意时候停止跳舞（也可以没有跳就直接结束）。当到达第一维为 $L$ 的顶点就不得不停止，因为该顶点没有出边。

假设白兔停止时，跳了 $m$ 步，白兔会把这只舞曲给记录下来成为一个序列。序列的第 $i$ 个元素为它第 $i$ 步经过的边。

问题来了：给定正整数 $k$ 和 $y$（$1\le y\le n$），对于每个 $t$（$0\le t<k$），求有多少种舞曲（假设其长度为 $m$）满足 $m \bmod k=t$，且白兔最后停在了坐标第二维为 $y$ 的顶点？

两支舞曲不同定义为它们的长度（$m$）不同或者存在某一步它们所走的边不同。

输出的结果对 $p$ 取模。

输入格式

输入文件名为 dance.in。

第一行五个用空格隔开的整数 $n,k,L,x,y,p$。

接下来 $n$ 行，每行有 $n$ 个用空格隔开的整数，第 $i$ 行的第 $j$ 个数表示 $w[i][j]$。

输出格式

输出文件名为 dance.out。

依次输出 $k$ 行，每行一个数表示答案对 $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

提示

样例解释 1

$t=0$：

1. 路径长度为 $0$，方案数为 $1$。
2. 路径长度为 $2$，一共有六类路径：
   • $(0,1)\to (1,1)\to (2,1)$ 该路径有 $w(1,1)\times w(1,1)=4$ 条；
   • $(0,1)\to (1,1)\to (3,1)$ 该路径有 $w(1,1)\times w(1,1)=4$ 条；
   • $(0,1)\to (2,1)\to (3,1)$ 该路径有 $w(1,1)\times w(1,1)=4$ 条；
   • $(0,1)\to (1,2)\to (2,1)$ 该路径有 $w(1,2)\times w(2,1)=1$ 条；
   • $(0,1)\to (1,2)\to (3,1)$ 该路径有 $w(1,2)\times w(2,1)=1$ 条；
   • $(0,1)\to (2,2)\to (3,1)$ 该路径有 $w(1,2)\times w(2,1)=1$ 条；

答案就为 $1+4+4+4+1+1+1=16$。

$t=1$：

1. 路径长度为 $1$，一共有三类路径：
   • $(0,1)\to (1,1)$ 该路径有 $w(1,1)=2$ 条；
   • $(0,1)\to (2,1)$ 该路径有 $w(1,1)=2$ 条；
   • $(0,1)\to (3,1)$ 该路径有 $w(1,1)=2$ 条；
2. 路径长度为 $3$，一共有三类路径：
   • $(0,1)\to (1,1)\to (2,1)\to (3,1)$ 该路径有 $w(1,1)\times w(1,1)\times w(1,1)=8$ 条；
   • $(0,1)\to (1,1)\to (2,2)\to (3,1)$ 该路径有 $w(1,1)\times w(1,2)\times w(2,1)=2$ 条；
   • $(0,1)\to (1,2)\to (2,1)\to (3,1)$ 该路径有 $w(1,2)\times w(2,1)\times w(1,1)=2$ 条；

答案就为 $2+2+2+8+2+2=18$。

数据范围

对于全部数据，$p$ 为一个质数，$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$ 为 $p-1$ 的约数，$1\le L\le 10^8$。

对于每组测试点，特殊限制如下：

• 测试点 $1,2$：$L\le 10^5$；
• 测试点 $3$：$n=1,w(1,1)=1$，$k$ 的最大质因子为 $2$；
• 测试点 $4$：$n=1$，$k$ 的最大质因子为 $2$；
• 测试点 $5$：$n=1,w(1,1)=1$；
• 测试点 $6$：$n=1$；
• 测试点 $7,8$：$k$ 的最大质因子为 $2$。