Bobo 听说 Babai 发现了一种用于图同构问题的拟多项式时间算法。 现在 Bobo 想要在多项式时间内解决……某些简单图上的问题。 实际上，Bobo 想要在一个连通图 $G = \langle V, E \rangle$ 上解决图自同构问题（定义如下），其中 $n$ 个顶点，$m$ 条边，且 $V = \{1, 2, \dots, n\}$。自同构 $\phi$ 是 $V$ 上的一个置换，满足对于所有 $\{x, y\} \in E$，都有 $\{\phi(x), \phi(y)\} \in E$。 Bobo 想要计算自同构的数量，结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含 2 个整数 $n, m$ ($3 \le n \le 2000, n \le m \le n + 4$)。 接下来的 $m$ 行中，第 $i$ 行包含 2 个整数 $a_i, b_i$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边 ($1 \le a_i, b_i \le n, a_i \neq b_i$)。 保证图是连通的且没有重边。

输出格式

一个整数，表示自同构的数量，对 $(10^9 + 7)$ 取模。

样例

样例输入 1

3 3
1 2
2 3
3 1

样例输出 1

6

样例输入 2

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

样例输出 2

4