010 - Make a lot

問題

長さ$N$の数列$A={A_1,A_2,...,A_N}$があり、最初、$A_i$の各要素は異なります。
また、$1 \leq B_i,C_i \leq N$を満たす$M$個の整数の組があります。
あなたは$M$個の整数の組から$K$個以下の整数の組を選んだあと、好きな回数以下の操作を行えます。
・$K$個の整数の組に含まれるものを一つ選んでその整数の組を$l,r$とし、$A_l$と$A_r$を入れ替える。
操作後の数列$A$としてあり得るものの個数が最大になるように$K$個の整数の組を選んだ時、操作後の数列$A$としてあり得るものの個数を998244353で割った余りを答えてください。

入力

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

$N$ $M$ $K$
$B_1$ $C_1$
$B_2$ $C_2$
...
$B_M$ $C_M$

1行目に整数$N,M,K$が与えられる。 2行目から$M$行にかけて整数$B_i,C_i(1 \leq i \leq M)$が与えられる。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N,M,K \leq 2×10^5$
• $K \leq M$
• $1 \leq B_i , C_i \leq N (1 \leq i \leq M)$

入出力例

入力例1

5 3 2
1 2
2 3
4 5

出力例1

6

$K$個の整数の組として、{1,2}{2,3}を選んだ時、操作後の数列として考えられるものは6通りです。

入力例2

1873 20 6
1 6
8 4
2 9
8 14
9 19
1 8
1 291
94 48
23 48
95 23
1 5
6 8
95 75
75 2
2 5
5 1
101 1011
1873 1
1873 5
95 8

出力例2

5040