题目描述

初始给定一个 \(n\) 个点 \(m\) 条边的无向图，现在需要你将每条边进行定向，即对于无向边 \((u,v)\) 定向成有向边 \(\lt u,v \gt\) 或 \(\lt v,u \gt \)，但是要求保证所有边定向后，每个顶点的入度最多为 \(1\)，问最终得到的有向图可能的方案数。

格式

输入格式

第一行两个整数 \(n\) 和 \(m\) ，分别表示点数和边数；

接下来\(m\)行，每行两个整数 \(u,v\) 表示点 \(u\) 和点 \(v\) 之间有一条边。

注意：同一对顶点之间可能有多条边，但算不同的边。

输出格式

一行一个整数 \(ans\)，表示所有可能的方案数对 \(10^9+7\) 取模后的值。

数据保证至少有一种满足条件的定向方案。

样例1

样例输入1

5 4
1 2
3 2
4 5
4 5

样例输出1

6

限制

\(20\%\)的数据：\(1≤ n ≤10\)。

\(40\%\)的数据：\(1≤ n ≤100\)。

\(100\%\)的数据：\(1≤ m ≤ n ≤100000\)。