I. Pizzas
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Matías is a renowned chef who has been specializing in pizzas lately.

Having prepared and tasted hundreds of pizzas, Matías noted pairs of ingredients (represented by integers) that have the same flavor.

This relationship of equal flavors is transitive, and sometimes out of laziness, Matías omits pairs that are already represented by the rest of the notes; for example, if he noted that pairs $$$(1, 2)$$$ and $$$(2, 3)$$$ have the same flavor, he may not note the pair $$$(1, 3)$$$ because it can be deduced that if $$$1$$$ tastes the same as $$$2$$$ and $$$2$$$ tastes the same as $$$3$$$, then $$$1$$$ tastes the same as $$$3$$$.

His friends, Javier, Víctor, and Lalo, gathered with Matías to make pizzas, and they came up with the following strategy:

  • Put all the ingredients in a randomly sorted list.
  • Check the ingredients one by one in the order of the list.
  • If the current ingredient would add a new flavor to the pizza according to Matías' notes and the ingredients already used, add it to the pizza. If not, do not add it.

Soon they realized, disappointed, that all the pizzas they made tasted the same. But Víctor, being the computer scientist of the group, became more interested in the total number of different pizzas that could be made with their strategy. Two pizzas are considered different if the sets of ingredients used in both are different.

Víctor quickly calculated the value and wants to confirm the answer with you. Given the number of ingredients and Matías' notes, calculate the number of different pizzas that can be formed modulo $$$10^9+7$$$ using the described strategy.

Input

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$m$$$ $$$(0 \leq m \leq \min(\frac{n(n-1)}{2}, 10^5))$$$, indicating the total number of ingredients and the number of pairs in Matías' notes.

The following $$$m$$$ lines contain two integers $$$a_i$$$, $$$b_i$$$ $$$(1 \leq a_i, b_i \leq n, a_i \neq b_i)$$$ each, indicating that ingredient $$$a_i$$$ has the same flavor as ingredient $$$b_i$$$ and vice versa. There are no repeated pairs in Matías' notes.

Output

An integer, indicating the number of different pizzas that can be formed modulo $$$10^9+7$$$ using the described strategy.

Examples
Input
5 3
1 3
2 4
3 5
Output
6
Input
20 9
1 9
2 6
2 16
6 20
7 13
8 15
10 20
16 18
17 18
Output
56
Note

In the first example case, pizzas can be formed with the following sets of ingredients: $$$\{1, 2\}$$$, $$$\{1, 4\}$$$, $$$\{3, 2\}$$$, $$$\{3, 4\}$$$, $$$\{5, 2\}$$$, $$$\{5, 4\}$$$.

Note that ingredients $$$1$$$ and $$$5$$$ have the same flavor (which is the same as the flavor of $$$3$$$), so they cannot be used together in the same pizza.

One possible way to make a pizza with ingredients $$$\{3, 2\}$$$ is with the following list of ingredients (after randomly sorting it): $$$[3, 5, 2, 1, 4]$$$. In this case, $$$3$$$ adds a new flavor and is added; $$$5$$$ has the same flavor as $$$3$$$, so it is not added; $$$2$$$ adds a new flavor and is added; $$$1$$$ has the same flavor as $$$3$$$, so it is not added; $$$4$$$ has the same flavor as $$$2$$$, so it is not added.