AT_tupc2023_n Do Not Turn Back

頂点に $ 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) $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

答えを出力せよ。

### 部分点 - 追加の制約 $ N \leq 15 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 1 \to 2 \to 3 \to 5 \to 4 \to 6, 1 \to 3 \to 2 \to 4 \to 5 \to 6 $ の $ 2 $ つが条件を満たします。 ### Sample Explanation 2 連続でなければ同じ辺を何度も通ることが可能です。 ### Constraints - $ 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) $ - 与えられるグラフは単純連結無向グラフである - 入力はすべて整数