C. 欧洲之旅

每测试点时间限制：2 秒
内存限制：256 兆字节

欧洲的地图可以用 $n$ 个城市表示，城市编号为 $1$ 到 $n$，它们之间由 $m$ 条双向道路连接，每条道路连接两个不同的城市。
长度为 $k$ 的一次旅行是一个由 $k+1$ 个城市构成的序列 $v_1, v_2, \dots, v_{k+1}$，使得对于每个 $1 \leq i \leq k$，存在一条道路连接相邻的两个城市 $v_i$ 和 $v_{i+1}$。

特殊旅行是指满足不连续两次使用同一条道路的旅行，即它是一个旅行，并且对于所有 $1 \leq i \leq k-1$，有 $v_i \neq v_{i+2}$。

给定一个整数 $k$，计算长度恰好为 $k$ 且起点和终点为同一城市的不同特殊旅行的数量。
由于答案可能很大，输出其对 $998244353$ 取模的结果。

输入
第一行包含三个整数 $n, m, k$（$3 \leq n \leq 100$，$1 \leq m \leq n(n-1)/2$，$1 \leq k \leq 10^4$）——分别表示城市数、道路数和需要计算的旅行长度。
接下来 $m$ 行，每行包含两个不同的整数 $a$ 和 $b$（$1 \leq a, b \leq n$），表示连接城市 $a$ 和 $b$ 的一条道路。
保证所有道路互不相同（即每对城市之间至多有一条直接道路）。

输出
输出一个整数，表示长度为 $k$、起点与终点相同的特殊旅行的数量，对 $998244353$ 取模。

示例

示例 1
输入

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

输出

0

示例 2
输入

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

输出

12

示例 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

输出

35551130

注释
在第一个样例中，我们寻找长度为 $2$ 的特殊旅行，但因为不能连续两次使用同一条道路，一旦离开某个城市就无法立即返回，所以答案是 $0$。

在第二个样例中，共有如下 $12$ 个长度为 $3$ 且起点与终点相同的特殊旅行：
$(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)$、$(4,2,1,4)$。