分数: 100 点
问题陈述
有一个简单的有向图 G 与 N 顶点,编号 1, 2, \ldots, N.
对于每个 i 和 j (1 \leq i, j \leq N),给你一个整数 a_{i, j} 表示是否存在来自Vertex的有向边 i to j。 如果 a_{i, j} = 1,有一条来自顶点的有向边 i to j;如果 a_{i, j} = 0,没有。
找出长度不同的有向路径的数量 K in G,模数 10^9 + 7。 我们还将计算多次穿过同一条边的路径。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 50
- 1 \leq K \leq 10^{18}
- a_{i, j} is 0 or 1.
- a_{i, i} = 0
输入
输入由标准输入按以下格式给出:
N K
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}
输出
打印长度不同的有向路径的数量 K in G,模数 10^9 + 7.
示例输入 1
4 2 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0
示例输出 1
6
G 如下图所示:

有六个长度的有向路径 2:
- 1 → 2 → 3
- 1 → 2 → 4
- 2 → 3 → 4
- 2 → 4 → 1
- 3 → 4 → 1
- 4 → 1 → 2
示例输入 2
3 3 0 1 0 1 0 1 0 0 0
示例输出 2
3
G 如下图所示:

存在三个长度的有向路径 3:
- 1 → 2 → 1 → 2
- 2 → 1 → 2 → 1
- 2 → 1 → 2 → 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
示例输出 3
1
G 如下图所示:

存在一条长度为 的有向路径 2:
- 4 → 5 → 6
示例输入 4
1 1 0
示例输出 4
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
示例输出 5
957538352
请务必打印模数计数 10^9 + 7.