길이가 K인 경로

면접 대비

시간 제한2초메모리 제한512 MB

요약

방향 그래프의 인접 행렬이 주어질 때 길이 K인 경로의 개수를 10^9+7로 나눈 나머지를 구한다. K는 10^9까지 클 수 있다.

난이도: 보통10점 중 6점
유형: 행렬, 그래프, 분할 정복, 수학
정답자: 아직 제출이 없습니다

문제

천나라에는 마을이 $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

예제3

예제 1
입력
```
4 2
0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0
```
예상 출력
```
6
```
예제 2
입력
```
4 1
0 1 1 0
0 0 1 0
0 0 0 1
1 0 0 0
```
예상 출력
```
5
```
예제 3
입력
```
1 1
0
```
예상 출력
```
0
```