問題文

頂点に 1 から N の番号が、辺に 1 から M の番号が付いた N 頂点 M 辺の単純連結無向グラフ G が与えられます。辺 i\;(1 \leq i \leq M) は頂点 u_i と v_i を結んでいます。
正の整数 K が与えられるので、頂点 1 から頂点 N への長さ K の歩道であって、同じ辺を連続して通らないものの個数を 998244353 で割った余りを求めてください。
厳密には、以下をすべて満たす長さ K+1 の数列 a=(a_0,a_1,\dots,a_K) の個数を 998244353 で割った余りを求めてください。

• a_i は 1 以上 N 以下の整数 (0 \leq i \leq K)
• a_0=1, a_K=N
• G において a_{i-1} と a_{i} を直接結ぶ辺が存在する (1 \leq i \leq K)
• a_{i-2} \ne a_i (2 \leq i \leq K)

制約

• 3 \leq N \leq 100
• N-1 \leq M \leq \dfrac{N(N-1)}{2}
• 1 \leq K \leq 10^9
• 1 \leq u_i < v_i \leq N
• i \ne j のとき (u_i,v_i) \neq (u_j,v_j)
• 与えられるグラフは単純連結無向グラフである
• 入力はすべて整数

部分点

• 追加の制約 N \leq 15 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

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

出力例 1

2

1 \to 2 \to 3 \to 5 \to 4 \to 6, 1 \to 3 \to 2 \to 4 \to 5 \to 6 の 2 つが条件を満たします。

入力例 2

11 11 2023
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 11

出力例 2

1

連続でなければ同じ辺を何度も通ることが可能です。

入力例 3

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

出力例 3

405422475