問題文

頂点に $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$ で割った余りを出力せよ。

---

入力例 1

4 3 2
1 2
2 4
2 3

出力例 1

2

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

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

---

入力例 2

4 0 10

出力例 2

10000

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

---

入力例 3

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

出力例 3

120

---

入力例 4

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

出力例 4

838338733

---

入力例 5

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

出力例 5

418104233