问题陈述
《天长地久-一-》是今年推出的一款获奖网络游戏。该游戏因其可扮演的大量角色而迅速闻名。
在这个游戏中,角色的特点是 属性。该游戏中有$N$个属性,编号为$1$到$N$。每个属性采用两种状态之一, 光 or 黑暗。这意味着这个游戏中有$2^N$种角色。
你可以通过换工作来改变你的性格。尽管这是改变角色属性的唯一方法,但您可以根据需要多次更换职业。
换工作的规则有点复杂。当且仅当存在两个属性 $a$ 和 $b$ 且满足以下四个条件时,才可以将字符从 $A$ 更改为 $B$:
角色$A$的属性$a$的状态是 光.
角色$B$的属性$b$的状态是 光.
不存在属性 $c$ 使得字符 $A$ 和 $B$ 都具有 光 属性 $c$ 的状态。
一对属性 $(a, b)$ 是 兼容.
这里,我们说一对属性 $(a, b)$ 是 兼容 如果存在满足以下三个条件的属性序列 $c_1, c_2, \ldots, c_n$:
$c_1 = a$。
$c_n = b$。
$(c_i, c_{i+1})$ 或 $(c_{i+1}, c_i)$ 是所有 $i = 1, 2, \ldots, n-1$ 的特殊对。您将获得特殊对的列表。
既然你热情地喜欢这个游戏,你就会尝试与所有角色一起玩游戏(这真的很疯狂)。然而,您立即注意到,通过该游戏的转职规则,可以将一个角色更改为一组有限的角色。我们说字符 $A$ 和 $B$ 是 本质上不同 如果您无法通过重复作业更改将字符 $A$ 更改为字符 $B$。
那么,自然会出现以下问题;有多少个本质上不同的角色? 由于输出可能非常大,因此您应该以 $1{,}000{,}000{,}007$ 为模来计算答案。
输入
输入是一系列数据集。 数据集数量不超过 $50$,输入总大小不超过 $5$ MB。
每个数据集的格式如下。
$N$ $M$
$a_1$ $b_1$
:
:
$a_M$ $b_M$
每个数据集的第一行包含两个整数 $N$ 和 $M$($1 \le N \le 10^5$ 和 $0 \le M \le 10^5$)。 然后是 $M$ 行。 第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \lt b_i \le N$),表示第 $i$ 个特殊对。 输入以两个零终止。
如果$i \ne j$,则保证$(a_i, b_i) \ne (a_j, b_j)$。
输出
对于每个数据集,输出本质上不同的字符数以 $1{,}000{,}000{,}007$ 为模。
示例输入
3 2 1 2 2 3 5 0 100000 0 0 0
样本输入的输出
3 32 607723520