問題文

$N$ 頂点の単純有向グラフ $G$ があります。 頂点には $1, 2, \\ldots, N$ と番号が振られています。

各 $i, j$ ($1 \\leq i, j \\leq N$) について、頂点 $i$ から $j$ への有向辺の有無が整数 $a_{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$ で割った余りを出力することを忘れずに。