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$.