PinkRabbit is a winner.

Fuzhou City can be abstracted as an undirected graph with $n$ vertices and $m$ edges, containing no multiple edges or self-loops. PinkRabbit lives at vertex $1$, and his girlfriend lives at vertex $2$.

One day, PinkKitten casts a great spell, turning all edges in this undirected graph into directed edges. Now, PinkRabbit is concerned about whether he can meet his girlfriend.

Specifically, PinkRabbit can meet his girlfriend if and only if there exists a vertex $u$ such that in the new graph, there is a path from vertex $1$ to $u$, and there is also a path from vertex $2$ to $u$.

You need to calculate how many of the $2^m$ possible ways to orient all $m$ edges allow PinkRabbit to meet his girlfriend. You only need to output the result modulo $10^9 + 7$.

Input

The first line contains three positive integers $n$, $m$, and $id$. $n$ and $m$ are the number of vertices and edges in the graph, and $id$ is the subtask number.

The next $m$ lines each contain two positive integers $x$ and $y$, describing an edge.

Output

Output a single integer representing the answer.

Examples

Input 1

3 2 1
1 3
2 3

Output 1

3

Note 1

For this example, $id = 1$, which satisfies the $m \le 20$ constraint for subtask 1. There are 3 valid configurations: (1) $1 \to 3$, $2 \to 3$ (2) $1 \to 3$, $3 \to 2$ (3) $3 \to 1$, $2 \to 3$

Input 2

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

Output 2

30

Input 3

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

Output 3

55

Subtasks

This problem uses bundled subtask testing.

• Subtask 1 (30 points): $m \le 20$;
• Subtask 2 (15 points): There is a unique simple path between $1$ and $2$;
• Subtask 3 (20 points): $n \le 10$;
• Subtask 4 (35 points): No special constraints.

For all data, $1 \le n \le 15$, $1 \le m \le \frac{n(n-1)}{2}$, $1 \le x < y \le n$.