C. European Triptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe 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.InputThe 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).OutputPrint the number of special trips of length k which begin and end in the same city, modulo 998\,244\,353.ExamplesInput
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
NoteIn 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).
4 5 2
4 1
2 3
3 1
4 3
2 4

0 
['dp', 'graphs', 'math', 'matrices']