403555: GYM101193 F Cactus

In Mexico far, far away, huge cactus plantations are spread all over the country. And also there live novice crooks Carlos and Pedro. Once they watched the film “The Godfather” and decided to become famous mafia bosses. But the serious arm ang drug dealers haven’t taken them to their gangs. So they decided to sell cactuses to the ardent foreign collectors.

When they arrived to the plantation, Carlos and Pedro found that it is impossible to carry away a huge thorny cactus in the hands. Then the unlucky bandits decided to cut it into pieces that are no more than two edges.

Calculate the possible number of different ways to cut a poor cactus. Print this big as Carlos and Pedro’s sorrow number modulo 10⁹ + 7.

P.S. Cactus is a connected undirected graph in which every vertex belongs to no more than one simple cycle. In this problem vertex is the same as a thorn. Two ways are considered to be different if there is an edge between the thorns in one way and there is no edge between the same thorns in the other.

The first line of each test case contains two integer numbers n (the number of vertices) and m (the number of edges). The next m lines contain two integer numbers u_i and v_i (vertices connected by edges). It is guaranteed that there are no loops and multiple edges in the cactus graph.

Output the required number of cactus cuts modulo 10⁹ + 7.

3 2
1 2
2 3

4

2 1
1 2

2

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

20