Description

The Pantanal wetland is known as the largest wetland in the world. It is located in the southern part of Mato Grosso do Sul in central Brazil. Every rainy season, waves sparkle and life flourishes here, attracting many tourists.

To make the visit more interesting, several stone piers and stone bridges were built in the middle of a pond. Each stone bridge connects two stone piers, and between any two stone piers there is at most one bridge. This attraction has never been opened to the public because there are many dangerous piranhas in the pond.

Mr. Doudou loves adventure. As soon as he heard the news, he hurried to the pond, wanting to be the first person to walk on the bridges. Although he is adventurous, he does not want to risk his life, so he conducted careful field research and reached some startling conclusions: the routes of the piranhas are periodic, and the period can only be $2$, $3$, or $4$ units of time. In each unit of time, a piranha can swim from one stone pier to another. Upon arriving at a stone pier, if there is someone on it, it will attack; otherwise, it continues its periodic movement. If it is not at a stone pier, it will not attack.

With advanced instruments, Doudou quickly figured out all the movement patterns of the piranhas, and he started planning his own route. In each unit of time, he can only walk along a bridge from one stone pier to another, and he is not allowed to stay on any pier without moving, because standing still also involves other dangers. If Doudou and a piranha arrive at the same stone pier at the same time, he will be attacked by the piranha, which he certainly wants to avoid.

Doudou has selected two stone piers $\mathrm{Start}$ and $\mathrm{End}$. He wants to start from $\mathrm{Start}$ and be standing on $\mathrm{End}$ after exactly $K$ units of time. Assume that stone piers may be revisited (including $\mathrm{Start}$ and $\mathrm{End}$). He asks you to compute how many such routes exist (of course without being attacked by any piranha).

Input Format

The input consists of $M + 2 + \mathrm{NFish}$ lines.

The first line contains five positive integers $N, M, \mathrm{Start}, \mathrm{End}, K$, representing the number of stone piers, the number of stone bridges, the indices of $\mathrm{Start}$ and $\mathrm{End}$, and the required units of time for a route, respectively. Stone piers are numbered from $0$ to $N - 1$.

Lines $2$ to $M + 1$ give the information about the stone bridges. Each of these lines contains two integers $x$ and $y$, $0 \leq x, y \leq N - 1$, indicating that the bridge connects the piers numbered $x$ and $y$.

Line $M + 2$ contains an integer $\mathrm{NFish}$, the number of piranhas.

Lines $M + 3$ to $M + 2 + \mathrm{NFish}$ each describe one piranha. The first integer is $T$, with $T = 2, 3$ or $4$, indicating the period of the piranha’s movement. Then follow $T$ numbers describing the route within one period.

• If $T = 2$, the next $2$ numbers are $P_0$ and $P_1$: the piranha moves from $P_0$ to $P_1$, from $P_1$ to $P_0$, $\ldots$.
• If $T = 3$, the next $3$ numbers are $P_0, P_1$ and $P_2$: the piranha moves from $P_0$ to $P_1$, from $P_1$ to $P_2$, from $P_2$ to $P_0$, $\ldots$.
• If $T = 4$, the next $4$ numbers are $P_0, P_1, P_2$ and $P_3$: the piranha moves from $P_0$ to $P_1$, from $P_1$ to $P_2$, from $P_2$ to $P_3$, from $P_3$ to $P_0$, $\ldots$.

At the time Doudou starts, all piranhas are at position $P_0$ on their routes. Rest assured, this position will not be the $\mathrm{Start}$ pier.

Output Format

Output the number of routes. Since this number may be large, output the remainder when it is divided by $10000$.

6 8 1 5 3
0 2
2 1
1 0
0 5
5 1
1 4
4 3
3 5
1
3 0 5 1

2

Hint

For $100\%$ of the testdata, $1 \leq N \leq 50$, $1 \leq K \leq 2 \times 10^9$, $1 \leq \mathrm{NFish} \leq 20$.

Translated by ChatGPT 5