题目描述

给定一个无向图 $G_1$，它有 $k$ 个顶点，编号为 $0,1,\ldots,k-1$。

现在构造一个新图 $G_2$：

1. 取 $n$ 份互不相交的 $G_1$ 副本；
2. 第 $i$ 份副本中的顶点编号整体增加 $ik$，于是所有顶点最终编号为 $0,1,\ldots,kn-1$；
3. 对当前得到的整张图取补图：两个不同顶点在 $G_2$ 中相连，当且仅当它们在取补图之前不相连。

哈密顿路径是一条恰好经过图中每个顶点一次的路径。路径可以从任意顶点开始、在任意顶点结束。访问序列不同的两条路径视为不同，例如 $(0,1,2,3)$ 与 $(3,2,1,0)$ 是两条不同的路径。

求 $G_2$ 中哈密顿路径的数量，对 $998244353$ 取模。

输入格式

第一行包含三个整数 $k,m,n$，其中 $m$ 是 $G_1$ 的边数。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示 $G_1$ 中有一条无向边连接 $a_i$ 与 $b_i$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

数据范围

• $1\le k\le 14$；
• $0\le m\le k(k-1)/2$；
• $1\le n\le 50000$；
• 图中没有自环和重边。

样例

输入

3 2 2
0 1
1 2

输出

152