URI Online Judge | 1713
# Teletransport

**Timelimit: 1**

By Vinícius "Cabessa" Fernandes dos Santos Brazil

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.

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 ^{30}** ), indicating respectively the number of spaceships and the number of trips in the ticket. The second line of a test case contains two integers

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 ^{4}** , where

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 |