M. March and Conquer
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Marco Molo is a famous walking traveler in the distant kingdom of Mlogomia. The kingdom has $$$N$$$ cities and $$$M$$$ bidirectional paths. Each path connects two different cities, allowing direct walking from one to the other. The geometry in Mlogomia is extremely peculiar, and all paths have exactly the same length.

Marco intends to travel from Factorial to Primorial, the two most important cities in Mlogomia. Each day he is willing to walk between $$$1$$$ and $$$K$$$ paths, having to rest at night to continue his journey the next day.

Marco does not care about the total number of paths he has to walk to go from Factorial to Primorial, but he does want to ensure that he uses the least number of days possible. How many different ways can Marco make his journey? Since this value can be very large, it must be calculated modulo $$$998244353$$$.

A daily walk of Marco can be described with a sequence of $$$t+1$$$ cities, such that $$$1 \le t \leq K$$$ and there is a path between each city and the next. Two daily walks are different if they differ in the number of cities, or if the $$$i$$$-th city is not the same in both walks.

A journey of Marco can be described with a sequence of $$$d$$$ daily walks, such that the first walk starts in Factorial, the last walk ends in Primorial, and each walk ends in the same city where the next one begins. Moreover, $$$d$$$ is minimal, meaning it is impossible to travel from Factorial to Primorial with fewer walks. Two journeys are different if the $$$i$$$-th daily walk of one differs from the corresponding walk in the other.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 2000$$$ and $$$1 \leq M,K \leq 2000$$$), which indicate respectively the number of cities in Mlogomia, the number of paths, and the maximum number of paths Marco can walk in a day. Each city is identified by a distinct integer between $$$1$$$ and $$$N$$$, with Factorial being city $$$1$$$ and Primorial being city $$$2$$$.

Each of the following $$$M$$$ lines describes a path by two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U,V \leq N$$$ and $$$U \neq V$$$), which indicate the two cities that this path connects. It is guaranteed that there are no two different paths connecting the same pair of cities.

Output

A single line with one integer, indicating the number of different journeys Marco can make, modulo $$$998244353$$$.

Examples
Input
4 3 2
1 3
3 4
4 2
Output
2
Input
4 3 5
1 3
3 4
4 2
Output
4
Input
10 1 100
1 5
Output
0
Note

In the first example, the two possible journeys are as follows:

  • The first day's walk is $$$1, 3$$$ and the second is $$$3, 4, 2$$$.
  • The first day's walk is $$$1, 3, 4$$$ and the second is $$$4, 2$$$.
Note that both journeys require $$$d=2$$$ days, which is the minimum number of days needed to go from Factorial to Primorial in this case.

For the second example, one of the $$$4$$$ possible journeys uses a single daily walk $$$1, 3, 4, 3, 4, 2$$$. Notice that it is valid to repeat cities in a walk.