#P1662C. European Trip

European Trip

Description

The map of Europe can be represented by a set of nn cities, numbered from 11 through nn, which are connected by mm bidirectional roads, each of which connects two distinct cities. A trip of length kk is a sequence of k+1k+1 cities v1,v2,,vk+1v_1, v_2, \ldots, v_{k+1} such that there is a road connecting each consecutive pair viv_i, vi+1v_{i+1} of cities, for all 1ik1 \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+1k+1 cities v1,v2,,vk+1v_1, v_2, \ldots, v_{k+1} such that it forms a trip and vivi+2v_i \neq v_{i + 2}, for all 1ik11 \le i \le k - 1.

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

The first line contains three integers nn, mm and kk (3n1003 \le n \le 100, 1mn(n1)/21 \le m \le n(n - 1) / 2, 1k1041 \le k \le 10^4) — the number of cities, the number of roads and the length of trips to consider.

Each of the following mm lines contains a pair of distinct integers aa and bb (1a,bn1 \le a, b \le n) — each pair represents a road connecting cities aa and bb. 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 kk which begin and end in the same city, modulo 998244353998\,244\,353.

Input

The first line contains three integers nn, mm and kk (3n1003 \le n \le 100, 1mn(n1)/21 \le m \le n(n - 1) / 2, 1k1041 \le k \le 10^4) — the number of cities, the number of roads and the length of trips to consider.

Each of the following mm lines contains a pair of distinct integers aa and bb (1a,bn1 \le a, b \le n) — each pair represents a road connecting cities aa and bb. 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 kk which begin and end in the same city, modulo 998244353998\,244\,353.

Sample Input 1

4 5 2
4 1
2 3
3 1
4 3
2 4

Sample Output 1

0

Sample Input 2

4 5 3
1 3
4 2
4 1
2 1
3 4

Sample Output 2

12

Sample Input 3

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

Sample Output 3

35551130

Note

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

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