One-

Problem Statement

"Everlasting -One-" is an award-winning online game launched this year. This game has rapidly become famous for its large number of characters you can play.

In this game, a character is characterized by attributes. There are $N$ attributes in this game, numbered $1$ through $N$. Each attribute takes one of the two states, light or darkness. It means there are $2^N$ kinds of characters in this game.

You can change your character by job change. Although this is the only way to change your character's attributes, it is allowed to change jobs as many times as you want.

The rule of job change is a bit complex. It is possible to change a character from $A$ to $B$ if and only if there exist two attributes $a$ and $b$ such that they satisfy the following four conditions:

• The state of attribute $a$ of character $A$ is light.

• The state of attribute $b$ of character $B$ is light.

• There exists no attribute $c$ such that both characters $A$ and $B$ have the light state of attribute $c$.

• A pair of attribute $(a, b)$ is compatible.

Here, we say a pair of attribute $(a, b)$ is compatible if there exists a sequence of attributes $c_1, c_2, \ldots, c_n$ satisfying the following three conditions:

• $c_1 = a$.

• $c_n = b$.

• Either $(c_i, c_{i+1})$ or $(c_{i+1}, c_i)$ is a special pair for all $i = 1, 2, \ldots, n-1$. You will be given the list of special pairs.

Since you love this game with enthusiasm, you are trying to play the game with all characters (it's really crazy). However, you have immediately noticed that one character can be changed to a limited set of characters with this game's job change rule. We say character $A$ and $B$ are essentially different if you cannot change character $A$ into character $B$ by repeating job changes.

Then, the following natural question arises; how many essentially different characters are there? Since the output may be very large, you should calculate the answer modulo $1{,}000{,}000{,}007$.

Input

The input is a sequence of datasets. The number of datasets is not more than $50$ and the total size of input is less than $5$ MB.

Each dataset is formatted as follows.

$N$ $M$ $a_1$ $b_1$ : : $a_M$ $b_M$

The first line of each dataset contains two integers $N$ and $M$ ($1 \le N \le 10^5$ and $0 \le M \le 10^5$). Then $M$ lines follow. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i \lt b_i \le N$) which denote the $i$-th special pair. The input is terminated by two zeroes.

It is guaranteed that $(a_i, b_i) \ne (a_j, b_j)$ if $i \ne j$.

Output

For each dataset, output the number of essentially different characters modulo $1{,}000{,}000{,}007$.

Sample Input

3 2 1 2 2 3 5 0 100000 0 0 0

Output for the Sample Input

3 32 607723520

Example

Input

3 2 1 2 2 3 5 0 100000 0 0 0

Output

3 32 607723520

inputFormat

outputFormat

output may be very large, you should calculate the answer modulo $1{,}000{,}000{,}007$.

Input

The input is a sequence of datasets. The number of datasets is not more than $50$ and the total size of input is less than $5$ MB.

Each dataset is formatted as follows.

$N$ $M$ $a_1$ $b_1$ : : $a_M$ $b_M$

The first line of each dataset contains two integers $N$ and $M$ ($1 \le N \le 10^5$ and $0 \le M \le 10^5$). Then $M$ lines follow. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i \lt b_i \le N$) which denote the $i$-th special pair. The input is terminated by two zeroes.

It is guaranteed that $(a_i, b_i) \ne (a_j, b_j)$ if $i \ne j$.

Output

For each dataset, output the number of essentially different characters modulo $1{,}000{,}000{,}007$.

Sample Input

3 2 1 2 2 3 5 0 100000 0 0 0

Output for the Sample Input

3 32 607723520

Example

Input

3 2 1 2 2 3 5 0 100000 0 0 0

Output

3 32 607723520

样例

3 2
1 2
2 3
5 0
100000 0
0 0

3
32
607723520

</p>