Problem Description

Mr. $ E869120 $, the leader of the operation team for the Paken Camp, has a connected undirected graph with $ N $ vertices and $ M $ edges. The $ i $-th edge connects vertices $ a_i $ and $ b_i $.

On December 24th, which is Christmas Eve, he plans to color the graph and present it to Mr. $ reiji1112 $, the head of the Paken Club. However, vertices directly connected by an edge should not be colored the same, as it would not look good. Therefore, vertices directly connected by an edge must be painted in different colors.

There are $ K $ colors prepared, numbered as color $ 1 $, $ 2 $, $ 3 $, ..., $ K $. How many ways are there to color the graph? Find the answer modulo $1\ 000\ 000\ 007$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ a_3 $ $ b_3 $ ... $ a_M $ $ b_M $

Output Format

Find the number of ways to color the graph modulo $1\ 000\ 000\ 007$.

Sample Input and Output

Sample Input #1

3 2 2
1 2
2 3

Sample Output #1

2

Sample Input #2

3 2 5
1 2
2 3

Sample Output #2

80

Sample Input #3

4 3 1
1 2
2 3
2 4

Sample Output #3

0

Sample Input #4

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

Sample Output #4

972

Sample Input #5

10 10 100
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10
4 8

Sample Output #5

332858118

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $100\ 000$ inclusive.
• $ M $ is an integer between $ 1 $ and $100\ 003$ inclusive.
• $ M - N $ is $ 3 $ or less.
• $ K $ is an integer between $ 1 $ and $1\ 000\ 000\ 000$ inclusive.
• $ a_i, b_i $ are integers between $ 1 $ and $ N $ inclusive.
• $ a_i < b_i $ for $(1 \leq i \leq M)$.
• $(a_i, b_i) \neq (a_j, b_j)$ for $(i \neq j)$.

Subtasks

Subtask $ 1 $ [$ 4 $ points]
The input satisfies the following conditions:

• $N \leq 8$.
• $K \leq 2$.

Subtask $ 2 $ [$ 13 $ points]

• $N \leq 8$.

Subtask $ 3 $ [$ 8 $ points]

• $ M - N = -1 $ and $ a_i = i, b_i = i + 1 $ for $(1 \leq i \leq M)$.

Subtask $ 4 $ [$ 13 $ points]

• $M - N \leq -1$.

Subtask $ 5 $ [$ 13 $ points]

• $M - N \leq 0$.

Subtask $ 6 $ [$ 13 $ points]

• $M - N \leq 1$.

Subtask $ 7 $ [$ 13 $ points]

• $M - N \leq 2$.

Subtask $ 8 $ [$ 23 $ points]

• No additional constraints.

Sample Explanation 1

The following $ 2 $ ways of coloring satisfy the conditions:

Sample Explanation 2

This input example does not satisfy the constraints of Subtask $ 1 $ but satisfies the constraints of Subtasks $ 2 $ to $ 8 $.

Sample Explanation 5

Find the answer modulo $1\ 000\ 000\ 007$.

见题面 Input 部分

见题面 Output 部分