Um_nik 有一个简单的连通无向图，具有以下性质： 对于图中任意 $k+1$ 个顶点的子集 $A$，存在两个顶点 $a, b \in A$ 和一条边 $e$，使得从 $a$ 到 $b$ 的所有路径都包含边 $e$。

请帮他求出该图邻接矩阵的行列式，结果对 $998\,244\,353$ 取模。

输入格式

第一行包含三个整数 $n, m, k$：图的顶点数、边数以及给定的参数 ($1 \le n \le 25\,000, n-1 \le m \le 500\,000, 1 \le k \le 25$)。

接下来 $m$ 行描述图的边。每行包含两个整数 $u$ 和 $v$：由边连接的两个顶点 ($1 \le u, v \le n, u \neq v$)。

保证该图是连通的，且对于图中任意 $k+1$ 个顶点的子集 $A$，存在两个顶点 $a, b \in A$ 和一条边 $e$，使得从 $a$ 到 $b$ 的所有路径都包含边 $e$。保证图中不包含重边。

输出格式

输出一个整数：Um_nik 的图的邻接矩阵的行列式，对 $998\,244\,353$ 取模。

样例

输入 1

4 3 1
1 2
2 3
3 4

输出 1

1

输入 2

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

输出 2

998244352

输入 3

10 15 10
1 8
1 7
6 7
2 8
6 9
1 2
4 9
4 10
4 6
5 6
3 8
9 10
8 10
3 5
2 7

输出 3

35

说明