题目描述

AtCoder 共有 $N$ 个城市，分别被称为 City $1$、City $2$、$\\ldots$、City $N$。最初，每对不同城市之间都有一条双向道路，但其中 $M$ 条路由于时间推移而变得无法使用。具体而言，对于每个 $1\\leq i \\leq M$，连接 City $U_i$ 和 City $V_i$ 的道路已经无法使用。

Takahashi 将进行一次从 City $1$ 开始并以 City $1$ 结束的为期 $K$ 天的旅行。严格来说，从 City $1$ 开始并以 City $1$ 结束的为期 $K$ 天的旅行是一个包含 $K+1$ 个城市 $(A_0, A_1, \\ldots, A_K)$ 的序列，满足 $A_0=A_K=1$，对于每个 $0\\leq i\\leq K-1$，$A_i$ 和 $A_{i+1}$ 不同且仍然存在连接 City $A_i$ 和 City $A_{i+1}$ 的可用道路。

请打印以 City $1$ 开始并以 City $1$ 结束的为期 $K$ 天的不同旅行数量，结果取模 $998244353$。这里，当存在一个 $i$ 使得 $A_i\\neq B_i$ 时，两个 $K$ 天旅行 $(A_0, A_1, \\ldots, A_K)$ 和 $(B_0, B_1, \\ldots, B_K)$ 被认为是不同的。

约束条件

• $2 \\leq N \\leq 5000$
• $0 \\leq M \\leq \\min\\left( \\frac{N(N-1)}{2},5000 \\right)$
• $2 \\leq K \\leq 5000$
• $1 \\leq U_i<V_i \\leq N$
• 输入中所有的 $(U_i, V_i)$ 对都是两两不同的。
• 输入中的所有值均为整数。

输入

从标准输入中以以下格式给出输入：

$N$ $M$ $K$ $U_1$ $V_1$ $:$ $U_M$ $V_M$

输出

打印答案。

示例输入1

3 1 4
2 3

示例输出1

4

有四种不同的旅行方式，如下所示。

• ($1,2,1,2,1$)
• ($1,2,1,3,1$)
• ($1,3,1,2,1$)
• ($1,3,1,3,1$)

其他旅行方式都不合法，因此我们应该打印 $4$。

示例输入2

3 3 3
1 2
1 3
2 3

示例输出2

0

没有可用的道路，因此没有有效的旅行。

示例输入3

5 3 100
1 2
4 5
2 3

示例输出3

428417047