#P17508. PM14250 哈密顿路径计数

PM14250 哈密顿路径计数

题目描述

给定一个无向图 G1G_1,它有 kk 个顶点,编号为 0,1,…,k−10,1,\ldots,k-1。

现在构造一个新图 G2G_2:

  1. 取 nn 份互不相交的 G1G_1 副本;
  2. 第 ii 份副本中的顶点编号整体增加 ikik,于是所有顶点最终编号为 0,1,…,kn−10,1,\ldots,kn-1;
  3. 对当前得到的整张图取补图:两个不同顶点在 G2G_2 中相连,当且仅当它们在取补图之前不相连。

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

求 G2G_2 中哈密顿路径的数量,对 998244353998244353 取模。

输入格式

第一行包含三个整数 k,m,nk,m,n,其中 mm 是 G1G_1 的边数。

接下来 mm 行,每行两个整数 ai,bia_i,b_i,表示 G1G_1 中有一条无向边连接 aia_i 与 bib_i。

输出格式

输出一个整数,表示答案对 998244353998244353 取模后的结果。

数据范围

  • 1≤k≤141\le k\le 14;
  • 0≤m≤k(k−1)/20\le m\le k(k-1)/2;
  • 1≤n≤500001\le n\le 50000;
  • 图中没有自环和重边。

样例

输入

3 2 2
0 1
1 2

输出

152