A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 $n$ 座城市组成，$m$ 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 $1,000,000,007({10}^9+7)$ 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

输入格式

第一行包含两个正整数 $n,m$，分别表示城市的个数和双向道路的数量。

接下来 $m$ 行，每行包含两个正整数 $u_i,v_i$，描述一条连接 $u_i$ 和 $v_i$ 的双向道路。保证没有重边和自环。

输出格式

输出一行包含一个整数，表示建造军营和看守道路的方案数对 ${10}^9+7$ 取模的结果。

样例一

input

2 1
1 2

output

5

explanation

A 国有两座城市，一条道路连接他们。所有可能的方案如下：

• 在城市 $1$ 建军营, 不看守这条道路;
• 在城市 $1$ 建军营, 看守这条道路;
• 在城市 $2$ 建军营, 不看守这条道路;
• 在城市 $2$ 建军营, 看守这条道路;
• 在城市 $1,2$ 建军营, 看守这条道路。

样例二

input

4 4
1 2
2 3
3 1
1 4

output

184

样例三

见下发文件中的 ex_barrack3.in 与 ex_barrack3.ans。

样例四

见下发文件中的 ex_barrack4.in 与 ex_barrack4.ans。

子任务

对所有数据，保证 $1\le n\le 5\times {10}^5$，$n-1\le m\le {10}^6$，$1\le u_i,v_i\le n$，$u_i\ne v_i$。

各测试点的信息如下

特殊性质 $\mathrm{A}$：保证 $m=n-1$ 且第 $i$ 条道路连接城市 $i$ 与 $i+1$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$