bee 1713 - Teletransport

The Galactic Confederation installed a new teletransport system in its spaceships. Each spaceship received a teletransport cabin, in which there is a panel with four buttons. Each button is labeled with a different letter A, B, C or D and with a number which indicates the spaceship to which the user will be instantly transported if the respective button is pressed (as everyone knows, Confederation spaceships are identified by integers from 1 to N ).

To use the system, the user must buy a ticket for each trip he wishes to make (one trip equals one button press). Notice that as the number of buttons in the panel is small compared to the number of Confederation spaceships, the user may have to buy a multiple ticket of L trips to go from a given spaceship S to another spaceship T.

For example, for the spaceships in the figure below, if the user is inside the cabin of spaceship 3 and presses button B he is transported to spaceship 2. If he has a multiple ticket and presses button B again he is then transported to spaceship 1.

Your task in this problem is, given the start spaceshift S, the destination spaceship T , and the number of trips L of a ticket, to determine the number of distinct sequences of L buttons that take the user from spaceship S to spaceship T . For example, for the spaceships in the figure above, there are four distinct sequences of L = 2 buttons that take the user from spaceship S = 3 to spaceship T = 1: CD, DA, AB, and BB.

Input

The input contains several test cases. The first line of a test case contains two integers N (1 ≤ N ≤ 100) and L (0 ≤ L < 2³⁰ ), indicating respectively the number of spaceships and the number of trips in the ticket. The second line of a test case contains two integers S and T (1 ≤ S, T ≤ N ), indicating respectively the start spaceship and the destination spaceship. Each of the following N lines describes the panel in the cabin of a spaceship. The i-th line (1 ≤ i ≤ N ) contains four integers A, B, C and D (1 ≤ A, B, C, D ≤ N ), representing the numbers attached to the four buttons in the teletransport cabin of spaceship number i.

Output

For each test case in the input your program must produce a single line, containing a single integer, which must be equal to r module 10⁴ , where r is the number of distinct sequences of L buttons that take the user from spaceship S to spaceship T.

Sample Input	Sample Output
2 20 1 1 2 2 2 2 1 1 1 1 2 29 1 1 2 2 2 2 1 1 1 1 2 0 1 1 2 2 2 2 1 1 1 1 2 0 1 2 2 2 2 2 1 1 1 1 3 2 3 1 1 2 2 2 2 1 3 2 2 2 3 1	7776 0 1 0 4

Sample Input

Sample Output

2 20

1 1

2 2 2 2

1 1 1 1

2 29

1 1

2 2 2 2

1 1 1 1

2 0

1 1

2 2 2 2

1 1 1 1

2 0

1 2

2 2 2 2

1 1 1 1

3 2

3 1

1 2 2 2

2 1 3 2

2 2 3 1

7776