配点 : $100$ 点

問題文

$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$ で割った余りを出力せよ。

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

6

$G$ は次図です。

長さ $2$ の有向パスは、次の $6$ 通りです。

• $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$ の有向パスは、次の $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$ の有向パスは、次の $1$ 通りです。

• $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$ で割った余りを出力することを忘れずに。