题目描述

贝西和她附近农场的牛朋友们最终决定，他们将开始通过小径将他们的农场连接在一起，以形成一个反对农民的联盟。$\red{N }$个$\red{（1 <= N <= 100,000）}$个农场中的每一个奶牛最初被指示建立一条通往另一个农场的小径，总共有 $\red{N }$条小径。然而，在项目进行了几个月后，实际上只建造了 $\red{M (1 <= M < N) }$的这些小径。

农场之间已经建立了一条小径的农场之间的争论现在威胁到分裂奶牛联盟。为了缓解紧张局势，$\red{Bessie }$希望计算出目前存在的 $\red{M }$条小径可以建造多少种方式。例如，如果有一条连接农场 $\red{3 }$和 $\red{4 }$的小径，那么一种可能性是农场 $\red{3 }$建造了这条小径，另一种可能性是农场 $\red{4 }$建造了这条小径。帮助 $\red{Bessie }$通过计算不同路径分配给建造它们的农场的数量，以 $\red{1,000,000,007 }$为模。如果在每个分配中至少有一条由不同农场建造的小径，则两个分配被认为是不同的。

给出$\red{n}$个点$\red{m}$条边的图，现把点和边分组，每条边只能和相邻两点之一分在一组，点可以单独一组，问分组方案数。

输入格式

第 $\red{1 }$行：两个空格分隔的整数 $\red{N }$和 $\red{M}$

第 $\red{2..1+M }$行：第 $\red{i+1 }$行描述第 $\red{i }$条路径。每行包含两个以空格分隔的整数 $\red{u_i }$和 $\red{v_i (1 <= u_i, v_i <= N, u_i != v_i) }$描述由小径连接的农场对。

输出格式

第 $\red{1 }$行：包含分配给农场的路径数量的单行，取模 $\red{1,000,000,007}$。如果没有分配满足上述条件，则输出 $\red{0}$。

样例

输入样例1

5 4 
1 2 
3 2 
4 5 
4 5

输出样例1

6

输入样例2

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

输出样例2

0

提示

请注意，同一对农场之间可以有两条路径。

有 $\red{6 }$种可能的分配。令 $\red{\{a,b,c,d\} }$表示农场 $\red{1 }$构建路径 $\red{a，}$农场 $\red{2 }$构建路径 $\red{b，}$农场 $\red{3 }$构建路径 $\red{c，}$农场 $\red{4 }$构建路径 $\red{d，}$分配为：

$\red{\{2, 3, 4, 5\} }$

$\red{\{2, 3, 5, 4\} }$

$\red{\{1, 3, 4, 5\} }$

$\red{\{1, 3, 5, 4\} }$

$\red{\{1, 2, 4, 5\} }$

$\red{\{1, 2, 5, 4\} }$