Teleportation

Time limit2sMemory limit512 MB

Summary

Count length-L button sequences that move from ship S to ship T, where each ship has four outgoing transitions, modulo 10^4.

Level: Medium6 of 10
Topics: Matrix, Dynamic programming, Graph
Solved: No attempts yet

Problem

The Galactic Confederation installed a new teleport system on its spaceships. Every ship has one teleport booth, and inside the booth there is a panel with four buttons. Each button carries a different letter, A, B, C or D, together with the number of the destination ship the user is transported to, instantly, when that button is pressed. Confederation ships are identified by the integers 1 to $N$ .

To use the system the user buys a ticket for each trip, and one trip is one button press. The panel has few buttons compared with the number of ships in the Confederation, so travelling from a ship $S$ to another ship $T$ may require a ticket for $L$ trips.

Look at the ships in the figure below. In the teleport booth of ship 3, pressing button B transports the user to ship 2. With trips left on the ticket, pressing button B again transports the user to ship 1.

Given the departure ship $S$ , the arrival ship $T$ and the number of trips $L$ written on the ticket, count the distinct button sequences that take the user from ship $S$ to ship $T$ . A sequence has exactly $L$ presses. For the ships in the figure, four distinct sequences with $L = 2$ take a user from ship $S = 3$ to ship $T = 1$ : CD, DA, AB and BB.

Input

The first line contains two integers $N$ and $L$ , the number of ships and the number of trips on the ticket. ( $1 \le N \le 100$ , $0 \le L < 2^{30}$ )

The second line contains two integers $S$ and $T$ , the departure ship and the arrival ship. ( $1 \le S, T \le N$ )

Each of the next $N$ lines describes the panel of one teleport booth. The $i$ -th of those lines contains four integers $A$ , $B$ , $C$ and $D$ , the numbers written on the four buttons of ship $i$ . ( $1 \le A, B, C, D \le N$ )

Output

Print one line with a single integer. Let $r$ be the number of distinct button sequences of length $L$ that take the user from ship $S$ to ship $T$ . Print $r$ modulo $10^4$ .

Examples5

Example 1
Input
```
2 20
1 1
2 2 2 2
1 1 1 1
```
Expected output
```
7776
```
Example 2
Input
```
2 29
1 1
2 2 2 2
1 1 1 1
```
Expected output
```
0
```
Example 3
Input
```
2 0
1 1
2 2 2 2
1 1 1 1
```
Expected output
```
1
```
Example 4
Input
```
2 0
1 2
2 2 2 2
1 1 1 1
```
Expected output
```
0
```
Example 5
Input
```
3 2
3 1
1 2 2 2
2 1 3 2
2 2 3 1
```
Expected output
```
4
```