Walk

题面翻译

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

题目描述

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

样例 #1

样例输入 #1

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

样例输出 #1

6

样例 #2

样例输入 #2

3 3
0 1 0
1 0 1
0 0 0

样例输出 #2

3

样例 #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

样例 #4

样例输入 #4

1 1
0

样例输出 #4

0

样例 #5

样例输入 #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