配点 : $500$ 点

問題文

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
• $(U_i, V_i)$ は全て互いに相異なる。
• 入力は全て整数である。

入力

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

$N$ $M$ $K$

$U_1$ $V_1$

$:$

$U_M$ $V_M$

出力

答えを出力せよ。

3 1 4
2 3

4

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

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

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

3 3 3
1 2
1 3
2 3

0

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

5 3 100
1 2
4 5
2 3

428417047