순간이동

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

요약

각 함선에 네 개의 이동 버튼이 있을 때, 배 S에서 출발해 정확히 L번 눌러 배 T에 도착하는 서로 다른 버튼 순서의 개수를 10^4로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 행렬, 동적 계획법, 그래프
정답자: 아직 제출이 없습니다

문제

은하 연합은 소속 우주선에 새로운 순간이동 장치를 설치했다. 우주선마다 순간이동실이 하나 있고, 그 안에는 버튼 네 개가 달린 조작판이 있다. 버튼에는 각각 A, B, C, D 중 서로 다른 문자가 붙어 있고, 그 버튼을 누르면 즉시 이동하게 되는 목적지 우주선의 번호가 함께 적혀 있다. 연합의 우주선은 1부터 $N$ 까지의 정수로 구분한다.

장치를 쓰려면 이동 한 번마다 표를 사야 한다. 버튼을 한 번 누르는 것이 이동 한 번이다. 조작판의 버튼 수는 연합의 우주선 수에 비해 적으므로, 어떤 우주선 $S$ 에서 다른 우주선 $T$ 로 가려면 $L$ 번 이동하는 표를 사야 할 수도 있다.

아래 그림의 우주선을 보자. 3번 우주선의 순간이동실에서 B 버튼을 누르면 2번 우주선으로 이동한다. 표에 이동 횟수가 남아 있어서 B 버튼을 한 번 더 누르면 1번 우주선으로 이동한다.

출발 우주선 $S$ , 도착 우주선 $T$ , 표에 적힌 이동 횟수 $L$ 이 주어질 때, 사용자를 우주선 $S$ 에서 우주선 $T$ 로 데려가는 서로 다른 버튼 열이 몇 개인지 구하라. 버튼 열의 길이는 정확히 $L$ 이다. 위 그림의 우주선에서 $S = 3$ , $T = 1$ , $L = 2$ 인 경우 CD, DA, AB, BB의 네 가지가 있다.

입력

첫째 줄에 우주선의 수 $N$ 과 표의 이동 횟수 $L$ 이 주어진다. ( $1 \le N \le 100$ , $0 \le L < 2^{30}$ )

둘째 줄에 출발 우주선의 번호 $S$ 와 도착 우주선의 번호 $T$ 가 주어진다. ( $1 \le S, T \le N$ )

이어지는 $N$ 개 줄은 우주선 한 대의 순간이동실 조작판을 나타낸다. 그중 $i$ 번째 줄에는 네 정수 $A$ , $B$ , $C$ , $D$ 가 주어지며, $i$ 번 우주선의 네 버튼에 적힌 번호다. ( $1 \le A, B, C, D \le N$ )

출력

한 줄에 정수 하나를 출력한다. 사용자를 우주선 $S$ 에서 우주선 $T$ 로 데려가는 길이 $L$ 의 서로 다른 버튼 열의 개수를 $r$ 이라 할 때, $r$ 을 $10^4$ 으로 나눈 나머지를 출력한다.

예제5

예제 1
입력
```
2 20
1 1
2 2 2 2
1 1 1 1
```
예상 출력
```
7776
```
예제 2
입력
```
2 29
1 1
2 2 2 2
1 1 1 1
```
예상 출력
```
0
```
예제 3
입력
```
2 0
1 1
2 2 2 2
1 1 1 1
```
예상 출력
```
1
```
예제 4
입력
```
2 0
1 2
2 2 2 2
1 1 1 1
```
예상 출력
```
0
```
예제 5
입력
```
3 2
3 1
1 2 2 2
2 1 3 2
2 2 3 1
```
예상 출력
```
4
```