HH has a constant habit: he likes to take a walk after meals. A "hundred-step walk" means walking a certain distance within a certain amount of time. However, HH also likes variety, so he will not immediately walk back along the path he just came from. Furthermore, because HH likes variety, the paths he takes every day are never exactly the same. He wants to know how many ways he can take his walk. You are given a map of the school (assume the length of every road is $1$). Find the number of valid paths of length $t$ from a given starting point $A$ to a given destination $B$.

Input

The first line contains five integers $N$, $M$, $t$, $A$, and $B$.

• $N$ is the number of intersections in the school.
• $M$ is the number of roads in the school.
• $t$ is the distance HH wants to walk.
• $A$ is the starting point of the walk.
• $B$ is the destination of the walk.

The next $M$ lines:

• Each line contains a pair $A_i$, $B_i$, indicating there is a road between intersection $A_i$ and intersection $B_i$.
• It is guaranteed that $A_i \ne B_i$, but it is not guaranteed that there is at most one road between any two intersections.
• Intersections are numbered from $0$ to $N-1$.
• All data on the same line are separated by a single space, with no extra spaces at the beginning or end of the line. There are no extra blank lines.

The answer should be taken modulo $45989$.

Output

A single line representing the answer.

Examples

Input 1

4 5 3 0 0
0 1
0 2
0 3
2 1
3 2

Output 1

4

Constraints

For $20\%$ of the data, $n \leq 4, m \leq 10, A = B = 0$.

An additional $10\%$ of the data, $n \leq 3, m \leq 3$.

An additional $10\%$ of the data, $m = 0$.

An additional $10\%$ of the data, $n \leq 10, m \leq 40$.

An additional $10\%$ of the data, $n \leq 10$.

An additional $10\%$ of the data, $A_i = 0$.

For $100\%$ of the data, $1 \leq N \leq 20, 1 \leq M \leq 60, 0 \leq t \leq 2^{30}, 0 \leq A,B < N$.