Problem Description

Niwango lives in the town of NicoNico, which has $N$ intersections numbered from $1$ to $N$. There are also $M$ roads connecting these intersections, each road numbered from $1$ to $M$. Traveling on road $i$ allows you to move from intersection $A_i$ to intersection $B_i$ or vice versa in $2^i$ time.

Niwango is about to go on a drive. He wants his route to start at intersection $1$, pass through all $M$ roads at least once, and return to intersection $1$. Determine the minimum time required for such a drive. Since the answer can be very large, output it modulo $1,000,000,007$.

Input Format

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$

• The first line contains two integers $N\ (2\ ≦\ N\ ≦\ 400,000)$ and $M\ (1\ ≦\ M\ ≦\ 500,000)$, representing the number of intersections and roads in NicoNico town, respectively.
• The next $M$ lines provide information about the roads. The $i$-th line contains two integers $A_i$ and $B_i\ (1\ ≦\ A_i\ ≦\ N,\ 1\ ≦\ B_i\ ≦\ N,\ A_i\ ≠\ B_i)$, indicating that road $i$ connects intersection $A_i$ and intersection $B_i$. No pair of intersections is connected by more than one road, and it is guaranteed that any intersection can be reached from any other intersection via some roads.

Output Format

Output the minimum time for the drive modulo $1,000,000,007$ on a single line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

70

Sample Input #2

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

Sample Output #2

2132

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $N\ ≦\ 2,525$ and $M\ ≦\ 2,525$, you will be awarded $40$ points.
• If you solve all test cases, you will receive an additional $70$ points.

Sample Explanation 1

In this example, the town has the following structure:  For instance, traversing the intersections in the order $1,2,3,4,2,3,1$ results in a time of $2^1\ +\ 2^3\ +\ 2^2\ +\ 2^5\ +\ 2^3\ +\ 2^4\ =\ 70$.

见题面 Input 部分

见题面 Output 部分