Problem Statement

There are $N$ cities numbered $0,1,\ldots,N-1$ and $M$ roads. Road $i$ allows bidirectional travel between city $s_i$ and city $t_i$.

Each city has an infinite number of people.

On day $0$, the first case of the Lambdos virus, $1$ infected person, appeared in city $0$.

The number of people infected with the Lambdos virus in a given city on day $i$ is always the sum of the numbers of infected people on day $i-1$ over all cities directly connected to that city by a road.

Find the number of people infected with the Lambdos virus in city $0$ on day $T$, modulo 998244353.

Input

$N$ $M$ $T$
$s_0$ $t_0$
$s_1$ $t_1$
$\vdots$
$s_{M-1}$ $t_{M-1}$

• $2 \leq N \leq 1 000$
• $1 \leq M \leq \min\left(\dfrac{N(N-1)}{2} ,1 000\right)$
• $1 \leq T \leq 1 000$
• $0 \leq s_{i} \lt t_{i} \leq N-1$
• All pairs $(s_i,t_i)$ are distinct
• All input values are integers

Output

Output the answer as an integer.

Sample

3 3 2
0 1
0 2
1 2

2

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

22

6 2 10
2 4
3 5

0

3 2 100
0 1
0 2

65980984