C. European Trip
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The map of Europe can be represented by a set of $$$n$$$ cities, numbered from $$$1$$$ through $$$n$$$, which are connected by $$$m$$$ bidirectional roads, each of which connects two distinct cities. A trip of length $$$k$$$ is a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that there is a road connecting each consecutive pair $$$v_i$$$, $$$v_{i+1}$$$ of cities, for all $$$1 \le i \le k$$$. A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that it forms a trip and $$$v_i \neq v_{i + 2}$$$, for all $$$1 \le i \le k - 1$$$.

Given an integer $$$k$$$, compute the number of distinct special trips of length $$$k$$$ which begin and end in the same city. Since the answer might be large, give the answer modulo $$$998\,244\,353$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$3 \le n \le 100$$$, $$$1 \le m \le n(n - 1) / 2$$$, $$$1 \le k \le 10^4$$$) — the number of cities, the number of roads and the length of trips to consider.

Each of the following $$$m$$$ lines contains a pair of distinct integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$) — each pair represents a road connecting cities $$$a$$$ and $$$b$$$. It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).

Output

Print the number of special trips of length $$$k$$$ which begin and end in the same city, modulo $$$998\,244\,353$$$.

Examples
Input
4 5 2
4 1
2 3
3 1
4 3
2 4
Output
0
Input
4 5 3
1 3
4 2
4 1
2 1
3 4
Output
12
Input
8 20 12
4 3
6 7
5 7
8 2
8 3
3 1
4 7
8 5
5 4
3 5
7 1
5 1
7 8
3 2
4 2
5 2
1 4
4 8
3 6
4 6
Output
35551130
Note

In the first sample, we are looking for special trips of length $$$2$$$, but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is $$$0$$$.

In the second sample, we have the following $$$12$$$ special trips of length $$$3$$$ which begin and end in the same city: $$$(1, 2, 4, 1)$$$, $$$(1, 3, 4, 1)$$$, $$$(1, 4, 2, 1)$$$, $$$(1, 4, 3, 1)$$$, $$$(2, 1, 4, 2)$$$, $$$(2, 4, 1, 2)$$$, $$$(3, 1, 4, 3)$$$, $$$(3, 4, 1, 3)$$$, $$$(4, 1, 3, 4)$$$, $$$(4, 3, 1, 4)$$$, $$$(4, 1, 2, 4)$$$, and $$$(4, 2, 1, 4)$$$.