Description

HH has an unchanging habit: he likes to walk one hundred steps after meals. By “one hundred steps,” he means taking a walk, that is, covering a certain distance within a certain time. However, HH also likes variety, so he will not immediately walk back along the road he just took. Since he likes variety, the path he takes each day is not exactly the same. He wants to know how many different ways he can take such a walk.

You are given the school’s map (assume every road has the same length, which is $1$). Find the number of valid paths of length $t$ from a given location $A$ to a given location $B$.

Input Format

The first line contains five integers $N, M, t, A, B$. Here $N$ is the number of intersections in the school, $M$ is the number of roads, $t$ is the distance HH wants to walk, $A$ is the starting point, and $B$ is the destination.

The next $M$ lines each contain a pair $A_i, B_i$, meaning there is a road from intersection $A_i$ to intersection $B_i$. It is guaranteed that $A_i \neq B_i$, but there may be multiple roads connecting the same pair of intersections. Intersections are numbered from $0$ to $N-1$. All data on the same line are separated by a single space, and there are no extra spaces at the beginning or end of lines. There are no extra blank lines.

Output Format

Output one line: the answer modulo $45989$.

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

4

Hint

Constraints and Conventions

For $30\%$ of the testdata, $N \le 4$, $M \le 10$, $t \le 10$.

For $100\%$ of the testdata, $N \le 50$, $M \le 60$, $t \le 2^{30}$, $0 \le A, B$.

Translated by ChatGPT 5