Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number, modulo 998244353, of ways to write an integer between 1 and K, inclusive, on each vertex of this graph to satisfy the following condition:

• two vertices connected by an edge always have different numbers written on them.

Input

The input is given from Standard Input in the following format:
N M K
u_1 v_1
u_2 v_2
$\vdots$
u_M v_M

Output

Print the number, modulo 998244353, of ways to write integers between 1 and K, inclusive, on the vertices to satisfy the condition.

Constraints

• $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$
• The given graph is simple.

Sample Input 1

4 3 2
1 2
2 4
2 3

Sample Output 1

2

Here are the two ways to satisfy the condition.

• Write 1 on vertices 1, 3, 4, and write 2 on vertex 2.
• Write 1 on vertex 2, and write 2 on vertex 1, 3, 4.

Sample Input 2

4 0 10

Sample Output 2

10000

All 10^4 ways satisfy the condition.

Sample Input 3

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

Sample Output 3

120

Sample Input 4

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

Sample Output 4

838338733

Sample Input 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

Sample Output 5

418104233

见题面 Input 部分

见题面 Output 部分