给定一个包含 $N$ 个顶点（编号为 $1$ 到 $N$）和 $M$ 条边（编号为 $1$ 到 $M$）的简单连通无向图 $G$。每条边 $1 \le i \le M$ 连接顶点 $u_i$ 和 $v_i$。

给定一个正整数 $K$，你需要求出从顶点 $1$ 到顶点 $N$ 长度为 $K$ 的路径数量，且要求路径中不能连续经过同一条边。

更正式地说，求长度为 $K+1$ 的序列 $a = (a_0, a_1, \dots, a_K)$ 的数量，需满足以下所有条件：

• 对于所有 $0 \le i \le K$，$a_i$ 是 $1$ 到 $N$ 之间的整数。
• $a_0 = 1$ 且 $a_K = N$。
• 对于所有 $1 \le i \le K$，$G$ 中存在直接连接 $a_{i-1}$ 和 $a_i$ 的边。
• 对于所有 $2 \le i \le K$，$a_{i-2} \neq a_i$。

计算满足上述条件的序列数量，并将结果对 $998244353$ 取模。

输入格式

输入通过标准输入按以下格式给出：

$N \ M \ K$ $u_1 \ v_1$ $u_2 \ v_2$ $\vdots$ $u_M \ v_M$

数据范围

• $1 \le N \le 100$
• $N - 1 \le M \le \frac{N(N - 1)}{2}$
• $1 \le K \le 10^9$
• $1 \le u_i < v_i \le N$ ($1 \le i \le M$)
• $G$ 是一个简单连通无向图。
• 所有输入值均为整数。

输出格式

在一行中输出答案。

样例

输入 1

6 8 5
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6

输出 1

2

输入 2

11 11 2023
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 11

输出 2

1

输入 3

7 21 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

输出 3

405422475

说明

在第一个样例中，$1 \to 2 \to 3 \to 5 \to 4 \to 6$ 和 $1 \to 3 \to 2 \to 4 \to 5 \to 6$ 均满足条件。