Strengthening of Bridges#3903
ByteLand is gearing up for military exercises, a significant event overseen by the Minister of Defense on-site. The Minister is particularly focused on the tank exercises.
ByteLand comprises several islands, some of which are linked by bridges. Each bridge connects two distinct islands, and no two islands are connected by more than one bridge. The ByteLanders are known for their frugality, so each island is connected by at most two bridges.
While the event plan is still in development, it is known that the tanks will need to travel from one island to another using various bridges. The specific bridges used are not predetermined. Many of ByteLand's bridges are old and not designed to support tanks. Consequently, the Minister of Defense has decided to reinforce certain bridges. The goal is to ensure that if travel was possible from island to island before reinforcement, it remains possible using the reinforced bridges. Since reinforcing a bridge is costly, the minister aims to reinforce the fewest number of bridges necessary.
The Minister of Defense wants to determine how many different ways there are to reinforce the minimum number of bridges. Two reinforcement strategies are considered different if there is at least one bridge that is reinforced in one strategy and not in the other. Help the Minister find the answer to this enduring question. Since the result can be large, provide the answer modulo 10^9+7.
The first line of input contains two integers and (1 \leq n \leq 10^5, 0 \leq m \leq 10^5) — the number of islands and the number of bridges in ByteLand, respectively.
The following lines each describe a bridge with two integers: v_i and u_i (1 \leq v_i, u_i \leq n, v_i \neq u_i) — the numbers of the islands connected by bridge .
Each bridge is listed no more than once in the input.
It is guaranteed that no more than two bridges connect to each island.
Output a single number: the remainder when the number of ways to reinforce the bridges is divided by 10^9+7.
Example 1