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

For each ~i~ and ~j~ ~(1 \le i, j \le 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 \le N \le 50~
• ~1 \le K \le 10^{18}~
• ~a_{i,j}~ is ~0~ or ~1~.
• ~a_{i,i} = 0~

Input Specification

The first line will contain 2 space separated integers ~N, K~.

The next ~N~ lines will each contain ~N~ space separated integers, ~a_{i,j}~.

Output Specification

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

Explanation For Sample 1

~G~ is drawn in the figure below:

There are six directed paths of length ~2~:

• ~1 \to 2 \to 3~
• ~1 \to 2 \to 4~
• ~2 \to 3 \to 4~
• ~2 \to 4 \to 1~
• ~3 \to 4 \to 1~
• ~4 \to 1 \to 2~

Sample Input 2

3 3
0 1 0
1 0 1
0 0 0

Sample Output 2

3

Explanation For Sample 2

~G~ is drawn in the figure below:

There are three directed paths of length ~3~:

• ~1 \to 2 \to 1 \to 2~
• ~2 \to 1 \to 2 \to 1~
• ~2 \to 1 \to 2 \to 3~

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

Explanation For Sample 3

~G~ is drawn in the figure below:

There is one directed path of length ~2~:

• ~4 \to 5 \to 6~

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

Explanation For Sample 5

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