Problem Description

Country A and Country B are in a fierce conflict, and Country A plans to build some barracks on its own territory.

Country A's territory consists of $n$ cities connected by $m$ bidirectional roads, ensuring that any two cities can be reached directly or indirectly via roads. Country A intends to select one or more cities (at least one) and build a barracks in each of these cities.

It is well known that communication between barracks is crucial. However, Country A has received intelligence that Country B will attack one of its roads soon, but the specific target is unknown. If Country B's attack is successful, the road will be cut off, potentially causing two barracks in Country A to be unable to reach each other, which Country A wants to avoid at all costs. Therefore, Country A decides to guard several roads (it can be one or more, or none at all), confident that the guarded roads can withstand Country B's attack and remain intact.

Country A hopes to devise a plan for building barracks and guarding roads such that no matter which road Country B attacks, it will not result in two barracks being unable to reach each other. Now, please help Country A calculate the number of possible plans for building barracks and guarding roads. Since the number of plans can be very large, you only need to output the result modulo $1,000,000,007\left(10^{9}+7\right)$. Two plans are considered different if and only if there is at least one city with a barracks in one plan and without in the other, or at least one road is guarded in one plan and not in the other.

Input Format

The first line contains two positive integers $n, m$, representing the number of cities and the number of bidirectional roads, respectively.

The next $m$ lines each contain two positive integers $u_{i}, v_{i}$, describing a bidirectional road connecting $u_{i}$ and $v_{i}$. There are no duplicate edges or self-loops.

Output Format

Output a single line containing an integer, which is the number of plans for building barracks and guarding roads modulo $1,000,000,007\left(10^{9}+7\right)$.

Sample Input and Output

Input Sample #1

2 1
1 2

Output Sample #1

5

Input Sample #2

4 4
1 2
2 3
3 1
1 4

Output Sample #2

184

Input Sample #3

See the attached file barrack/barrack3.in

Output Sample #3

See the attached file barrack/barrack3.ans

Input Sample #4

See the attached file barrack/barrack4.in

Output Sample #4

See the attached file barrack/barrack4.ans

Notes

Sample 1 Explanation

Country A has two cities connected by one road. All possible plans are as follows:

• Build a barracks in city $1$, do not guard the road;
• Build a barracks in city $1$, guard the road;
• Build a barracks in city $2$, do not guard the road;
• Build a barracks in city $2$, guard the road;
• Build barracks in cities $1,2$, guard the road.

Data Size and Constraints

For all data, it is guaranteed that $1 \leq n \leq 5 \times 10^5$, $n - 1 \leq m \leq 10^6$, $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$.

The information for each test point is as follows:

Special Property $\mathrm{A}$: Guarantees $m=n-1$ and the $i$-th road connects city $i$ and city $i+1$.

见题面 Input 部分

见题面 Output 部分