Bessie와 이웃 농장의 소들은 농장들을 길로 연결해 농부들에 맞설 동맹을 만들기로 했습니다. 농장 $N$개($1 \le N \le 100,000$)는 각각 정확히 한 다른 농장으로 길 하나를 만들어 총 $N$개를 만들도록 지시받았습니다. 하지만 몇 달 뒤 만들어진 것은 $M$개뿐입니다($1 \le M < N$).

어느 농장이 길을 만들었는지 다투어 동맹이 갈라질 위기입니다. Bessie는 긴장을 풀고자 기존 길 $M$개를 만든 방법 수를 구하려 합니다. 3과 4 사이 길은 농장 3 또는 4가 만들 수 있습니다. 각 길을 만든 농장에 배정하는 경우 수를 1,000,000,007로 나눈 나머지로 구하세요. 적어도 한 길의 건설 농장이 다르면 다른 배정입니다.

입력

• 1번 줄: 공백으로 구분된 정수 $N$과 $M$.
• $2..1+M$번 줄: $i+1$번째 줄은 길 $i$를 나타내며 공백으로 구분된 $u_{i}$와 $v_{i}$가 연결된 농장입니다($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$).

출력

• 1번 줄: 배정 수를 1,000,000,007로 나눈 나머지. 조건을 만족하는 배정이 없으면 0을 출력하세요.

예제

입력 1

5 4
1 2
3 2
4 5
4 5

출력 1

6

참고

같은 두 농장 사이에 길 두 개가 있을 수 있습니다.

6가지 배정이 있습니다. $\{a,b,c,d\}$는 농장 1이 길 a, 2가 b, 3이 c, 4가 d를 만든다는 뜻이며 배정은 다음과 같습니다. $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

문제 작성: Mark Gordon, 2011