题目描述

JAG 大学 ICPC 学科有 (N) 名学生，编号为 (1) 到 (N)。有 (M) 对朋友关系，第 (i) 对表示学生 (a_i) 与 (b_i) 是朋友，可以互相联系。

期末考试将考 (N) 门课。初始时，学生 (i) 只拥有第 (i) 门课的过去试题。

你是学生 (1)。现在进行 (K) 次独立随机事件。每次事件中，从 (M) 条朋友关系中等概率随机选出一条，让这两个学生互相交流，并把双方掌握的过去试题信息取并集后都获得。

求 (K) 次事件结束后，学生 (1) 拥有的试题科目数量的期望，答案对 (998244353) 取模。

题目保证该期望可表示为分数 (P/Q)，且 (Q\not\equiv 0\pmod {998244353})。输出满足 (R Q\equiv P\pmod {998244353}) 的 (R)。

输入格式

输入包含多个数据集，数据集个数不超过 (50)。

每个数据集格式如下：

N M K
a1 b1
...
aM bM

(2\le N\le 10)，(1\le M\le N(N-1)/2)，(1\le K\le 50)。

朋友关系无自环且无重复。

输入以 0 0 0 结束。

输出格式

对每个数据集，输出一行一个整数，表示期望值模 (998244353) 的结果。

样例输入

4 3 2
1 2
1 4
3 4
4 3 9
2 3
2 4
3 4
10 20 30
3 5
6 4
1 6
1 8
7 2
9 3
2 3
6 10
1 9
3 10
2 8
4 10
5 1
7 3
10 8
4 9
3 8
10 1
5 9
4 5
0 0 0

样例输出

887328316
1
369808863