R - Walk

Time Limit: 2 sec / Memory Limit: 1024 MB

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


入力例 1

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

出力例 1

6

G は次図です。

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

  • 123
  • 124
  • 234
  • 241
  • 341
  • 412

入力例 2

3 3
0 1 0
1 0 1
0 0 0

出力例 2

3

G は次図です。

長さ 3 の有向パスは、次の 3 通りです。

  • 1212
  • 2121
  • 2123

入力例 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 通りです。

  • 456

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

Score : 100 points

Problem Statement

There is a simple directed graph G with N vertices, numbered 1, 2, \ldots, N.

For each i and j (1 \leq i, j \leq N), you are given an integer a_{i, j} that represents whether there is a directed edge from Vertex i to j. If a_{i, j} = 1, there is a directed edge from Vertex i to j; if a_{i, j} = 0, there is not.

Find the number of different directed paths of length K in G, modulo 10^9 + 7. We will also count a path that traverses the same edge multiple times.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 50
  • 1 \leq K \leq 10^{18}
  • a_{i, j} is 0 or 1.
  • a_{i, i} = 0

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of different directed paths of length K in G, modulo 10^9 + 7.


Sample Input 1

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

Sample Output 1

6

G is drawn in the figure below:

There are six directed paths of length 2:

  • 123
  • 124
  • 234
  • 241
  • 341
  • 412

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

G is drawn in the figure below:

There are three directed paths of length 3:

  • 1212
  • 2121
  • 2123

Sample Input 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

Sample Output 3

1

G is drawn in the figure below:

There is one directed path of length 2:

  • 456

Sample Input 4

1 1
0

Sample Output 4

0

Sample Input 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

Sample Output 5

957538352

Be sure to print the count modulo 10^9 + 7.