Paths of length K

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

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.

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

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