Military Camps and Guarded Roads

A nation A is planning to build military camps in some of its cities in response to an imminent attack from nation B. Nation A has a territory consisting of n cities connected by m bidirectional roads such that any two cities can reach each other (i.e. the graph is connected). A chooses one or more cities (at least one) in which to build a military camp. Communication between these camps is essential. However, intelligence indicates that nation B will soon attack one of the roads, but the target road is unknown. If the attacked road (if unguarded) is cut off, it might disconnect two camps – something A cannot allow.

To avoid this, nation A may assign troops to guard an arbitrary set of roads. The guarded roads are guaranteed to remain intact even if attacked, while any unguarded road will be cut off if attacked. Nation A wishes to select a set of cities on which to build camps and to choose a subset (possibly empty) of roads to guard so that no matter which road is attacked, the military camps (i.e. the chosen cities) remain connected by intact roads.

Note that if an unguarded road in the induced subgraph of chosen cities is a bridge (an edge whose removal disconnects the subgraph), then an attack on that road would disconnect some pair of camps. Thus, in any valid plan, every road connecting two chosen cities that is a bridge must be guarded. The other roads (either non‐bridge roads among chosen cities or roads with at least one endpoint not having a camp) can be arbitrarily chosen to be guarded or not.

Formally, let S be the chosen subset of cities (with S nonempty) and let W be the set of roads guarded. For every road r of the original m roads, if r ∉ W then r will be removed (if attacked). The plan is valid if for every road r, after removing r (if it is unguarded) the induced graph on S remains connected. Two plans are considered different if either the set S is different or the set W is different.

Your task is to compute the number of valid plans modulo \(10^9+7\).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ some reasonable limit), indicating the number of cities and roads. The following m lines each contain two integers u and v (1 ≤ u, v ≤ n, u ≠ v) representing a bidirectional road between cities u and v. The graph is guaranteed to be connected.

outputFormat

Output a single integer, the number of valid plans modulo \(10^9+7\).

sample

3 3
1 2
2 3
1 3

44