配点 : $600$ 点

問題文

頂点に $1$ から $N$ の、辺に $1$ から $M$ の番号がついた $N$ 頂点 $M$ 辺の単純無向グラフが与えられます。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結んでいます。

このグラフのそれぞれの頂点に $1$ 以上 $K$ 以下の整数を書きこむ方法のうち、次の条件を満たす方法の個数を $998244353$ で割った余りを求めてください。

• 辺で結ばれた頂点同士には異なる数が書きこまれている。

制約

• $1 \leq N \leq 30$
• $0 \leq M \leq \min \left(30, \frac{N(N-1)}{2} \right)$
• $1 \leq K \leq 10^9$
• $1 \leq u_i \lt v_i \leq N$
• 入力で与えられるグラフは単純

入力

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

$N$ $M$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

出力

条件を満たすように頂点に $1$ 以上 $K$ 以下の整数を書きこむ方法の個数を $998244353$ で割った余りを出力せよ。

4 3 2
1 2
2 4
2 3

2

条件を満たす整数の書きこみ方は次の $2$ 通りです。

• 頂点 $1, 3, 4$ に $1$ を、頂点 $2$ に $2$ を書きこむ。
• 頂点 $2$ に $1$ を、頂点 $1, 3, 4$ に $2$ を書きこむ。

4 0 10

10000

$10^4$ 通り全ての書きこみ方が条件を満たします。

5 10 5
3 5
1 3
1 2
1 4
3 4
2 5
4 5
1 5
2 3
2 4

120

5 6 294
1 2
2 4
1 3
2 3
4 5
3 5

838338733

7 12 1000000000
4 5
2 7
3 4
6 7
3 5
5 6
5 7
1 3
4 7
1 5
2 3
3 6

418104233