问题描述

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

对于任意$i$和$j$($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$取模。

---

示例输入1

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

示例输出1

6

图$G$如下所示：

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

• $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$的有向路径共有$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$的有向路径共有$1$条：

• $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$。