問題文

AtCoder国には $N$ 個の都市があり、都市 $1$ , 都市 $2$ , $\\ldots$ , 都市 $N$ と番号付けられています。 最初、どの $2$ つの相異なる都市の間も双方向に通れる道で結ばれていましたが、老朽化が進み、これらのうち $M$ 本の道が使えなくなってしまいました。具体的には $1\\leq i \\leq M$ について都市 $U_i$ と都市 $V_i$ を結ぶ道が使えなくなってしまいました。

いま、高橋君は都市 $1$ で始まり、都市 $1$ で終わる $K$ 日間の旅をしようと考えました。都市 $1$ で始まり、都市 $1$ で終わる $K$ 日間の旅とは、 $K+1$ 個の都市の列 $(A_0, A_1, \\ldots, A_K)$ であって、$A_0=A_K=1$ をみたし、 $0\\leq i\\leq K-1$ について $A_i$ と $A_{i+1}$ が相異なり、かつ都市 $A_i$ と都市 $A_{i+1}$ が現在も使用可能な道で結ばれているものを指します。

都市 $1$ で始まり、都市 $1$ で終わる $K$ 日間の相異なる旅の数を $998244353$ で割った余りを出力してください。ただし、 $2$ つの $K$ 日間の旅 $(A_0, A_1, \\ldots, A_K)$ と $(B_0, B_1, \\ldots, B_K)$ が相異なるとは、ある $i$ が存在して $A_i\\neq B_i$ となることを言います。

制約

• $2 \\leq N \\leq 5000$
• $0 \\leq M \\leq \\min\\left( \\frac{N(N-1)}{2},5000 \\right)$
• $2 \\leq K \\leq 5000$
• $1 \\leq U_i<V_i \\leq N$
• $(U_i, V_i)$ は全て互いに相異なる。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $U_1$ $V_1$ $:$ $U_M$ $V_M$

出力

答えを出力せよ。

入力例 1

3 1 4
2 3

出力例 1

4

次のような $4$ 種類の旅が存在します。

• ($1,2,1,2,1$)
• ($1,2,1,3,1$)
• ($1,3,1,2,1$)
• ($1,3,1,3,1$)

これ以外に条件をみたすようなものは無いため、 $4$ を出力します。

入力例 2

3 3 3
1 2
1 3
2 3

出力例 2

0

使える道が $1$ 本も残っておらず、条件をみたすような旅は存在しません。

入力例 3

5 3 100
1 2
4 5
2 3

出力例 3

428417047