题目描述

给定一个简单的无向图，具有 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条编号为 $1$ 到 $M$ 的边。边 $i$ 连接顶点 $u_i$ 和顶点 $v_i$。

计算满足以下条件的在该图的每个顶点上写入一个介于 $1$ 和 $K$（包括端点）之间的整数的方案数（模 $998244353$）：

• 通过一条边连接的两个顶点上的数值不相同。

约束条件

• $1 \leq N \leq 30$
• $0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)$
• $1 \leq K \leq 10^9$
• $1 \leq u_i < v_i \leq N$
• 给定图是简单图。

---

输入

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

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

输出

打印满足条件的在顶点上写入整数的方案数（模 $998244353$）。

---

示例输入 1

4 3 2
1 2
2 4
2 3

示例输出 1

2

满足条件的两种方案如下：

• 在顶点 $1, 3, 4$ 上写入 $1$，在顶点 $2$ 上写入 $2$。
• 在顶点 $2$ 上写入 $1$，在顶点 $1, 3, 4$ 上写入 $2$。

---

示例输入 2

4 0 10

示例输出 2

10000

满足条件的方案有 $10^4$ 种。

---

示例输入 3

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

示例输出 3

120

---

示例输入 4

5 6 294
1 2
2 4
1 3
2 3
4 5
3 5

示例输出 4

838338733

---

示例输入 5

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

示例输出 5

418104233