#AT18. Walk

Walk

Original Problem Statement (English)

Source: AtCoder Educational DP Contest - Problem R

Problem Statement

There is a simple directed graph GG with NN vertices, numbered 1,2,…,N1, 2, \ldots, N.

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

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

Constraints

  • All values in input are integers.
  • 1≤N≤501 \leq N \leq 50
  • 1≤K≤10181 \leq K \leq 10^{18}
  • ai,ja_{i, j} is 00 or 11.
  • ai,i=0a_{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 KK in GG, modulo 109+710^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

GG is drawn in the figure below:

There are six directed paths of length 22:

  • 11 → 22 → 33
  • 11 → 22 → 44
  • 22 → 33 → 44
  • 22 → 44 → 11
  • 33 → 44 → 11
  • 44 → 11 → 22

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

GG is drawn in the figure below:

There are three directed paths of length 33:

  • 11 → 22 → 11 → 22
  • 22 → 11 → 22 → 11
  • 22 → 11 → 22 → 33

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

GG is drawn in the figure below:

There is one directed path of length 22:

  • 44 → 55 → 66

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 109+710^9 + 7.