← 返回题目列表

AtCoder · dp_r

R. 步行

中文机器翻译题面 查看原题

分数: 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.