길이가 K인 경로

천나라에는 마을이 $N$개 있고, 마을마다 1번부터 $N$번까지 번호가 붙어 있다. 두 마을 사이에는 길이 있을 수도 있고 없을 수도 있으며, 길이 있다면 그 길의 길이는 모두 1이다. 길은 한쪽 방향으로만 지나갈 수 있다.

민호는 마을 사이의 연결 상태를 $N \times N$ 인접 행렬로 적어 두었다. 행렬의 $i$번 줄 $j$번 수가 1이면 $i$번 마을에서 $j$번 마을로 가는 길이 있고, 0이면 그 길은 없다. 대각선 원소가 1이면 그 마을에서 자기 자신으로 돌아오는 길이 있다는 뜻이다.

길이가 $K$인 경로는 마을 번호를 나열한 수열 $v_0, v_1, \dots, v_K$ 중에서 모든 $1 \le t \le K$에 대해 $v_{t-1}$번 마을에서 $v_t$번 마을로 가는 길이 있는 것을 말한다. 같은 마을을 여러 번 지나도 되고, $v_0$과 $v_K$에는 아무 제한이 없다. 수열이 한 자리라도 다르면 서로 다른 경로로 센다.

인접 행렬이 주어지면 길이가 $K$인 서로 다른 경로가 몇 개인지 구하는 프로그램을 작성하라.

첫째 줄에 $N$과 $K$가 공백 하나로 구분되어 주어진다. ($1 \le N \le 100$, $1 \le K \le 10^9$)

다음 $N$개의 줄에 인접 행렬이 주어진다. 각 줄에는 0 또는 1인 정수 $N$개가 공백으로 구분되어 있다.

길이가 $K$인 경로의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제에서 길이가 2인 경로는 다음 6개다.

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