题目描述

给出 $N$ 个点 $M$ 条边的（没有自环但可能有重边的）无向图，要求给每个点分配 $0$ 条或 $1$ 条与它相邻的边，使得每条边被分配恰好一次，求方案数。答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $N,M$，其中 $1 \le M < N \le 10^5$。

下面 $M$ 行，每行两个正整数 $u,v$ 表示一条无向边 $(u,v)$，其中 $1 \le u,v \le N$。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

5 4 
1 2 
3 2 
4 5 
4 5

输出 #1

6

输入输出样例 #2

输入 #2

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

输出 #2

0

说明/提示

样例 $1$ 的 $6$ 种方案如下。

$4$ 个数分别代表第 $1\sim 4$ 条边被分配给了哪个点：

{2, 3, 4, 5} 
{2, 3, 5, 4} 
{1, 3, 4, 5} 
{1, 3, 5, 4} 
{1, 2, 4, 5} 
{1, 2, 5, 4}