European Trip
Description
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$.
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).
Print the number of special trips of length $k$ which begin and end in the same city, 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$.
Samples
4 5 2
4 1
2 3
3 1
4 3
2 4
0
4 5 3
1 3
4 2
4 1
2 1
3 4
12
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
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)$.