問題文

$0,1,\dots ,N-1$ の番号のついた $N$ 個の都市と $M$ 本の道路があります。 道路 $i$ を使うことで、都市 $s_i$ と都市 $t_i$ を双方向に行き来できます。

各都市には無限に人間が居ます。

$0$ 日目に、都市 $0$ で初めてラムドスウイルスの感染者が $1$ 人出ました。

特定の都市における $i$ 日目のラムドスウイルスの感染者は常に、その都市と直接道路で行き来できるすべての都市の $i-1$ 日目の感染者の合計です。

$T$ 日目の都市 $0$ におけるラムドスウイルスの感染者数を 998244353 で割ったあまりを求めてください。

入力

$N$ $M$ $T$
$s_0$ $t_0$
$s_1$ $t_1$
$⋮$
$s_{M-1}$ $t_{M-1}$

• $2\le N\le 1000$
• $1\le M\le min({\displaystyle \frac{N(N-1)}{2}},1000)$
• $1\le T\le 1000$
• $0\le s_i<t_i\le N-1$
• 組 $(s_i,t_i)$ は全て相異なる
• 入力は全て整数である

出力

整数で出力してください。

サンプル

3 3 2
0 1
0 2
1 2

2

5 7 4
0 1
1 4
0 3
1 3
3 4
0 4
2 4

22

6 2 10
2 4
3 5

0

3 2 100
0 1
0 2

65980984