Bridge Reinforcement

Byteotia is preparing for military exercises. This is a very important event, so important that the Minister of Defense of Byteotia oversees the preparations on site. The Minister of Defense is worried about how the tank exercises will go.

Byteotia consists of islands, some of which are connected by bridges. Each bridge connects two distinct islands, and any two islands are directly connected by at most one bridge. The people of Byteotia are very thrifty, so at most two bridges lead to each island.

The plan of the event is not ready yet, but it is known that the plan of the tank exercises will be as follows: the tanks must travel from one island to another using some bridges, and it does not matter which bridges the tanks use. Many bridges in Byteotia were built long ago and are not suitable for tanks at all. Therefore, the Minister of Defense decided to reinforce some bridges. Specifically, he wants to reinforce several bridges so that, regardless of the exercise plan, the following condition holds: if it was possible to travel from island $u$ to island $v$, then after reinforcing some bridges it is possible to travel from island $u$ to island $v$ using reinforced bridges. Reinforcing a bridge is an expensive operation, so the Minister wants to reinforce the minimum number of bridges.

The Minister of Defense of Byteotia wants to know how many different ways there are to reinforce the minimum number of bridges. Two ways are considered different if there is a bridge that is reinforced in one way and not reinforced in the other. Help the Minister of Defense find the answer to the question that has been troubling him for a long time. Since the answer can be quite large, output it modulo $10^9+7$.

The first line of the input file contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $0 \le m \le 10^5$), the number of islands and the number of bridges in Byteotia, respectively. The next $m$ lines describe the bridges, one per line. Each bridge is given by two integers: $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$, $v_i \neq u_i$), the numbers of the islands connected by bridge $i$.

It is guaranteed that each bridge is given in the input file at most once.

It is guaranteed that at most two bridges lead out of each island.

Output a single number: the remainder of dividing the number of ways to reinforce bridges by $10^9+7$.

In the first example there are three ways to reinforce bridges: reinforce the bridges with numbers $\lbrace 1, 2, 4 \rbrace$, or $\lbrace 1, 3, 4 \rbrace$, or $\lbrace 2, 3, 4 \rbrace$.