006 - Forest

問題

$N \ $頂点$ \ M \ $辺のグラフが与えられます。このグラフは森です。
頂点には$ \ 1 \ $から$ \ N \ $までの番号が付けられており、$i \ (1 \leq i \leq M) \ $番目の辺は頂点$ \ a_i \ $と頂点$ \ b_i \ $を結ぶ無向辺です。
あなたはこのグラフの任意の$ \ 2 \ $頂点を結ぶような無向辺をいくつでも($1 \ $本以上)追加することができます。
次の条件を満たす辺の追加方法の総数を$ \ 998244353 \ $で割った余りを求めてください。

• 辺を追加した後のグラフは森である。
• 頂点$ \ 1 \ $から頂点$ \ N \ $までの最短距離は$ \ K \ $である。
• 頂点$ \ 1 \ $から頂点$ \ N \ $までの最短経路に追加した辺が全て含まれる。

なお、頂点$ \ 1 \ $から頂点$ \ N \ $までの最短経路とは頂点$ \ 1 \ $から頂点$ \ N \ $にたどり着くために通る辺の本数が最小となるような経路を表し、最短距離はその経路長です。
また、$ \ 2 \ $つの辺の追加方法について、そのどちらかにしか存在しない辺がある場合にのみ、この$ \ 2 \ $つの追加方法は異なるものとします。

入力

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

$N \ M \ K$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_M \ b_M$

出力

条件を満たす辺の追加方法の総数を$ \ 998244353 \ $で割った余りを出力せよ。
出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 2000$
• $0 \leq M \leq N - 1$
• $1 \leq K \leq 10^9$
• $1 \leq a_i,b_i \leq N$
• 与えられるグラフは森である。
• 入力は全て整数。

入出力例

入力例1

5 2 3
1 2
4 5

出力例1

3

条件を満たす辺の追加方法は次の$ \ 3 \ $通りがあります。

入力例2

4 3 2
1 2
2 3
4 3

出力例2

0

条件を満たす辺の追加方法は存在しません。