在 ICPCCamp 中有 $n$ 个城镇，编号为 $1, 2, \dots, n$，由 $m$ 条道路连接。

Bobo 想知道保留 $n - 1$ 条道路使得城镇保持连通的方法数。

注意，当且仅当任意两个城市之间都能互相到达时，称这些城镇是连通的。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示城市 $a_i$ 和 $b_i$ 之间有一条道路。

数据范围

• $1 \leq n \leq 10^5$
• $n < m < n + 100$
• $1 \leq a_i, b_i \leq n$
• 城镇由 $m$ 条道路连通。
• 测试用例数量不超过 $10$。

输出格式

对于每个测试用例，输出一个整数，表示方法数对 $(10^9 + 7)$ 取模的结果。

样例

样例输入 1

4 5
1 2
1 3
1 4
2 4
4 4
5 6
1 2
2 3
3 1
1 4
4 5
5 1

样例输出 1

3
9