B. 6th heaven
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
DIE meets HARD
凛として時雨, #5

Tommy is cataloging records in her music shop. She wants to arrange them onto a 1-dimensional shelf by record matrix number, but some of the ink has been scratched off. Given $$$n$$$ disks labeled $$$1$$$ to $$$n$$$, she has deduced the following $$$k$$$ relationships: in the $$$i$$$th relationship, she knows that two disks $$$a_i$$$ and $$$b_i$$$ are adjacent to each other. It is guaranteed that each unordered pair $$$(a_i, b_i)$$$ of disks is distinct. Given these $$$k$$$ conditions, determine how many ways she can catalog the disks mod $$$10^9+7$$$.

Input

The first line has two integers $$$n$$$ ($$$2\leq n \leq 10^5$$$) and $$$k$$$ ($$$1\leq k \leq 10^5$$$).

The next $$$k$$$ lines each contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\leq a_i \lt b_i\leq n$$$).

Output

Please print $$$-1$$$ if arranging the disks given the current conditions is impossible, otherwise print the number of ways Tommy can catalog the disks, modulo $$$10^9+7$$$.

Examples
Input
7 3
1 3
2 3
1 2
Output
-1
Input
7 5
1 2
2 5
1 3
4 6
3 4
Output
4
Input
100 10
2 6
4 95
8 38
24 57
34 46
35 58
35 95
37 65
40 60
53 93
Output
764445383
Note

In the first sample test case, there is no way to arrange the disks given the conditions.

In the second sample test case, there are four valid sequences: $$$\{5, 2, 1, 3, 4, 6, 7\}, \{7, 5, 2, 1, 3, 4, 6\}, \{6, 4, 3, 1, 2, 5, 7\}$$$, and $$$\{7, 6, 4, 3, 1, 2, 5\}$$$.