题目描述

给定一个简单图，有 $n$ 个点，$m$ 条边。其中第 $i$ 条边连接了 $a_i$ 与 $b_i$。目前每条边都没有方向。请计算，有多少种方案，可以为每一条边确定一个方向，使得每个点有且仅有一个边是进入方向的。

由于方案可能很多，输出答案模 $1,000,000,007$ 的余数。

注意简单图保证图上没有重边及自环。

输入格式

• 第一行：两个整数 $n$ 与 $m$
• 第二行到第 $m+1$ 行：在第 $i+1$ 行有两个整数 $a_i$ 与 $b_i$ 表示一条边

输出格式

• 单个整数：表示模 $1,000,000,007$ 的余数。

4 4
1 2
2 3
3 4
4 1

2

样例解释 1

1-->2 2-->3 3-->4 4-->1 1<--2 2<--3 3<--4 4<--1

数据范围

• $30\%$ 的数据，$1\leq n,m\leq10$
• $60\%$ 的数据，$1\leq n,m\leq2000$
• $100\%$ 的数据，$1\leq n,m\leq300,000$