Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, and a constant $c$, define the weight $f(S)$ of a subset of edges $S \subseteq E$ as follows:

• If there exist two edges $e_1, e_2 \in S$ that share a common vertex, then $f(S) = 0$.
• Otherwise, $f(S) = c^{|S|}$.

In other words, if $S$ is a matching in $G$, then $f(S) = c^{|S|}$; otherwise, $f(S) = 0$.

You are required to calculate:

$$g(G) = \sum_{S \subseteq E} f(S)$$

Since the answer may be very large, output the result modulo $10^9+7$.

Input

The first line contains three integers $n, m, c$.

Each of the next $m$ lines contains two integers $u, v$, describing an edge.

Output

Output a single integer representing the answer.

Examples

Input 1

3 3 3
1 2
1 3
2 3

Output 1

10

Input 2

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

Output 2

449

Input 3

30 15 6
1 2
1 3
1 4
2 3
2 4
3 4
5 6
7 8
9 10
11 12
13 14
15 16
16 17
17 18
19 20

Output 3

938250775

Input 4

See the provided files.

Subtasks

Please note that this problem is worth 7 points in total.

For all test cases, $1 \le n \le 40$, $0 \le m \le \binom{n}{2}$, $0 \le c < 10^9+7$. It is guaranteed that the graph contains no multiple edges or self-loops.

• Property A: Guaranteed $m = \binom{n}{2}$.
• Property B: Guaranteed $m \ge \binom{n}{2} - 10$.

Hint: The time limit for this problem is relatively strict; please pay attention to constant factors in your implementation. You may use the [Custom Test] feature to test the efficiency of your program on the judging system.

Hack

The Hack feature is available for this problem.