Given an undirected graph with $n$ vertices and $m$ edges. The graph has no multiple edges or self-loops, and it is guaranteed to be connected.

For an edge connecting two vertices $(a, b)$, we define its associated interval as $(\min(a, b), \max(a, b))$ (an open interval).

A graph is defined as "good" if and only if for any two edges, their associated intervals are either nested or disjoint.

Find the number of ways to relabel the vertices (out of $n!$ possible permutations) such that the resulting graph is good.

The answer should be taken modulo $10^9+7$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in the graph.

The next $m$ lines each contain two integers $u_i$ and $v_i$, representing the $i$-th edge connecting vertices $u_i$ and $v_i$ before relabeling.

Output

Output a single positive integer representing the answer modulo $10^9+7$.

Examples

Input 1

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

Output 1

8

Input 2

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

Output 2

288

Input 3

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

Output 3

0

Constraints

For $100\%$ of the data, $1 \leq n, m \leq 2 \times 10^5$.