题目描述

$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$ で割った余りを求めてください。 ただし、同じ辺を複数回通るような有向パスも数えるものとします。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$G$ の長さ $K$ の有向パスは何通りか？ $10^9\ +\ 7$ で割った余りを出力せよ。

题目大意

给一张有向简单图，给出邻接矩阵，求长度为 $K$ 的路径条数，答案对 $10^9+7$ 取模。

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

6

3 3
0 1 0
1 0 1
0 0 0

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

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

提示

制約

• 入力はすべて整数である。
• $1\ \leq\ N\ \leq\ 50$
• $1\ \leq\ K\ \leq\ 10^{18}$
• $a_{i,\ j}$ は $0$ または $1$ である。
• $a_{i,\ i}\ =\ 0$

Sample Explanation 1

$G$ は次図です。  長さ $2$ の有向パスは、次の $6$ 通りです。 - $1$ → $2$ → $3$ - $1$ → $2$ → $4$ - $2$ → $3$ → $4$ - $2$ → $4$ → $1$ - $3$ → $4$ → $1$ - $4$ → $1$ → $2$

Sample Explanation 2

$G$ は次図です。  長さ $3$ の有向パスは、次の $3$ 通りです。 - $1$ → $2$ → $1$ → $2$ - $2$ → $1$ → $2$ → $1$ - $2$ → $1$ → $2$ → $3$

Sample Explanation 3

$G$ は次図です。  長さ $2$ の有向パスは、次の $1$ 通りです。 - $4$ → $5$ → $6$

Sample Explanation 5

答えを $10^9\ +\ 7$ で割った余りを出力することを忘れずに。