순간이동

은하 연합은 소속 우주선에 새로운 순간이동 장치를 설치했다. 우주선마다 순간이동실이 하나 있고, 그 안에는 버튼 네 개가 달린 조작판이 있다. 버튼에는 각각 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$으로 나눈 나머지를 출력한다.