Paths of length K

Interview

Time limit2sMemory limit512 MB

Summary

Count the number of length-K walks in a directed graph given its adjacency matrix, where K can be as large as 10^9, and output the count modulo 10^9+7.

Level: Medium6 of 10
Topics: Matrix, Graph, Divide and conquer, Math
Solved: No attempts yet

Problem

The country of Cheon has $N$ villages, numbered 1 to $N$ . Between two villages there may or may not be a road, and every road has length 1. A road can be traveled in one direction only.

Minho wrote the connections between the villages into an $N \times N$ adjacency matrix. If the $j$ -th number on line $i$ is 1, there is a road from village $i$ to village $j$ ; if it is 0, that road does not exist. A 1 on the diagonal means the village has a road back to itself.

A path of length $K$ is a sequence of village numbers $v_0, v_1, \dots, v_K$ such that for every $1 \le t \le K$ there is a road from village $v_{t-1}$ to village $v_t$ . A path may pass through the same village several times, and $v_0$ and $v_K$ are unrestricted. Two paths count as different if their sequences differ in at least one position.

Given the adjacency matrix, count the different paths of length $K$ .

Input

The first line contains $N$ and $K$ , separated by one space. ( $1 \le N \le 100$ , $1 \le K \le 10^9$ )

Each of the next $N$ lines contains $N$ integers, each either 0 or 1, separated by spaces. Together they form the adjacency matrix.

Output

Print the number of paths of length $K$ modulo $10^9+7$ on one line.

Hint

In the first example the six paths of length 2 are:

1 → 2 → 3
1 → 3 → 4
2 → 3 → 4
3 → 4 → 1
4 → 1 → 2
4 → 1 → 3

Examples3

Example 1
Input
```
4 2
0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0
```
Expected output
```
6
```
Example 2
Input
```
4 1
0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0
```
Expected output
```
5
```
Example 3
Input
```
1 1
0
```
Expected output
```
0
```