Teleportation

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.

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$)

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$.