#AT18. Walk

Walk

[R] Walk(dp_r)

来源: AtCoder Educational DP Contest - Problem R 原题时限:2 秒 / 内存:1024 MB

题目描述

有一个 NN 个顶点的简单有向图 GG,顶点编号为 1,2,…,N1, 2, \ldots, N。

对于每对 i,ji, j(1≤i,j≤N1 \le i, j \le N),用整数 ai,ja_{i,j} 表示是否存在从顶点 ii 到顶点 jj 的有向边:ai,j=1a_{i,j} = 1 表示存在,ai,j=0a_{i,j} = 0 表示不存在。

求 GG 中长度为 KK 的不同有向路径的数目,对 109+710^9 + 7 取模。同一条边可以被重复经过。

输入格式

输入由标准输入按以下格式给出:

N K
a_{1,1} a_{1,2} \ldots a_{1,N}
:
a_{N,1} a_{N,2} \ldots a_{N,N}

输出格式

输出长度为 KK 的有向路径数对 109+710^9 + 7 取模的结果。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤501 \le N \le 50
  • 1≤K≤10181 \le K \le 10^{18}
  • ai,ja_{i,j} 为 00 或 11。
  • ai,i=0a_{i,i} = 0。

样例 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