问题陈述

有一个简单的有向图 $G$ ，其顶点为 $N$ ，编号为 $1, 2, \ldots, N$ 。

对于每个 $i$ 和 $j$ ( $1 \leq i, j \leq N$ ) $1 \leq i, j \leq N$ ），你会得到一个整数 $a_{i, j}$ ，表示顶点 $i$ 到 $j$ 之间是否有一条有向边。如果是 $a_{i, j} = 1$ ，则存在一条从顶点 $i$ 到 $j$ 的有向边，如果是 $a_{i, j} = 0$ ，则没有。

求 $G$ 中长度为 $K$ 的不同有向路径的数目，对 $10^9 + 7$ 取模。我们还将计算多次穿越同一条边的路径。

限制因素

• 所有输入值均为整数。
• $1 \leq N \leq 50$
• $1 \leq K \leq 10^{18}$
• $a_{i, j}$ 是 $0$ 或 $1$ 。
• $a_{i, i} = 0$

输入

输入内容由标准输入法提供，格式如下：

• $N$ $K$
• $a_{1, 1}$ $\ldots$ $a_{1, N}$
• $:$
• $a_{N, 1}$ $\ldots$ $a_{N, N}$

输出

打印 $G$ 中长度为 $K$ 的不同有向路径的数量，模数为 $10^9 + 7$ 。

4 2
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0

6

$G$ 如下图所示：

有六条长度为 $2$ 的有向路径：

• $1$ → $2$ → $3$
• $1$ → $2$ → $4$
• $2$ → $3$ → $4$
• $2$ → $4$ → $1$
• $3$ → $4$ → $1$
• $4$ → $1$ → $2$

3 3
0 1 0
1 0 1
0 0 0

3

$G$ 如下图所示：

有三条长度为 $3$ 的有向路径：

• $1$ → $2$ → $1$ → $2$
• $2$ → $1$ → $2$ → $1$
• $2$ → $1$ → $2$ → $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

$G$ 如下图所示：

有一条长度为 $2$ 的有向路径：

• $4$ → $5$ → $6$

1 1
0

0

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

记得对 $10^9 + 7$ 取余。

来源

https://atcoder.jp/contests/dp/tasks/dp_r