Problem Description

Despite successfully obtaining the alien invasion plans, "JYY" was surprised to find that the alien mothership's attacks on Earth are random! It is imperative to quickly deploy a defense network on Earth to withstand the alien mothership's attacks. The Earth's defense network consists of nodes and energy connections between nodes. The defense network can be seen as a simple undirected graph $G(V,E)$ with $n$ nodes and $m$ edges, where each defense node corresponds to a node in $V$ and each energy connection corresponds to an edge in $E$. Additionally, considering energy transmission efficiency during the construction of the defense network, each node in $G$ is included in at most one simple cycle.

The alien mothership's attacks are random. Each time an attack begins, "JYY" will select a subset of defense nodes $S \subseteq V$ and connect these nodes with energy connections to activate a sub-network of defense. In other words, "JYY" will choose a subset of edges $H(S) \subseteq E$ in $G$ that satisfies:

1. (Sub-network connectivity) If we create a new graph $G'(V, H(S))$, connecting nodes in $G$ with edges from $H(S)$, then for any selected defense nodes $x, y \in S$, they are connected in $G'$.

2. (Sub-network minimality) Under the condition of 1 (sub-network connectivity), the number of edges selected is minimal, i.e., $|H(S)|$ is minimal.

$H(S)$ is the Steiner Tree generated by the set of nodes $S$ in graph $G$, and $|H(S)|$ is the minimum cost to activate the sub-network of defense. Considering the random nature of the alien mothership's attacks, "JYY" wants you to calculate the expected cost of activating the defense sub-network:

$$\frac{1}{2^{|V|}} \sum_{S \subseteq V} |H(S)|$$

Input Format

The first line of input contains two integers $n, m$, representing the number of nodes and edges in the graph, respectively.

The next $m$ lines each contain two integers $u, v (1 \le u, v \le n)$, representing an edge in the graph. The input guarantees no self-loops or duplicate edges, and that each node is included in at most one simple cycle.

Output Format

Output a single line, representing the expected cost of activating the defense sub-network.

If the expected value is expressed as a simplified fraction $P/Q$, output the remainder of $P \cdot Q^{-1} \mod 1,000,000,007$, where $Q^{-1}$ is the unique integer satisfying $Q \cdot Q^{-1} \equiv 1 \ (\text{mod} \ 1,000,000,007)$.

Sample Input and Output

Sample Input #1

3 2
1 2
2 3

Sample Output #1

750000006

Sample Input #2

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

Sample Output #2

468750006

Notes/Hints

Sample Explanation

For Sample Input 1, which is a chain, the following cases exist:

1. $\{\}, \{1\}, \{2\}, \{3\}, |H(S)| = 0$;
2. $\{1, 2\}, \{2, 3\}, |H(S)| = 1$;
3. $\{1, 3\}, \{1, 2, 3\}, |H(S)| = 2$.

Thus, $P/Q = 3/4$, and $P \cdot Q^{-1} = 750,000,006$.

For Sample Input 2, $\sum_{S \subseteq V} |H(S)| = 174$, thus $P/Q = 87/32$, and $P \cdot Q^{-1} = 468,750,006 \mod 1,000,000,007$.

Data Range

For $20\%$ of the data, $1 \le n \le 8$.

For $40\%$ of the data, $1 \le n \le 20$.

For $100\%$ of the data, $1 \le n \le 200$.

见题面 Input 部分

见题面 Output 部分