#AT18. Walk
Walk
[R] Walk(dp_r)
来源: AtCoder Educational DP Contest - Problem R 原题时限:2 秒 / 内存:1024 MB
题目描述
有一个 个顶点的简单有向图 ,顶点编号为 。
对于每对 (),用整数 表示是否存在从顶点 到顶点 的有向边: 表示存在, 表示不存在。
求 中长度为 的不同有向路径的数目,对 取模。同一条边可以被重复经过。
输入格式
输入由标准输入按以下格式给出:
N K
a_{1,1} a_{1,2} \ldots a_{1,N}
:
a_{N,1} a_{N,2} \ldots a_{N,N}
输出格式
输出长度为 的有向路径数对 取模的结果。
数据范围
- 输入中的所有值均为整数。
- 为 或 。
- 。
样例 1
输入:
4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0
输出:
6
样例 2
输入:
3 3
0 1 0
1 0 1
0 0 0
输出:
3
样例 3
输入:
6 2
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 1
0 0 0 0 0 0
输出:
1
样例 4
输入:
1 1
0
输出:
0
样例 5
输入:
10 1000000000000000000
0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1
1 1 1 0 1 1 0 1 1 0
0 1 1 1 0 1 0 1 1 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 1 0 1
1 0 0 0 1 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 0
输出:
957538352