소들의 동맹

베시와 근처 농장의 소 친구들은 농부들에게 맞서는 동맹을 만들기 위해 농장들을 길로 잇기로 했습니다.

농장은 모두 $N$개입니다 ($1 \le N \le 100{,}000$). 원래 각 농장의 소들은 정확히 다른 한 농장으로 가는 길을 하나씩 짓기로 되어 있었으므로, 전체 계획에는 길이 $N$개 있었습니다. 하지만 지금까지 그중 $M$개의 길만 실제로 지어졌습니다 ($1 \le M < N$).

각 길은 두 농장을 잇고, 그 두 농장 중 정확히 한 농장이 그 길을 지었습니다. 모든 농장은 원래 길을 하나만 짓도록 정해져 있었으므로, 각 농장이 지은 길은 많아야 한 개입니다.

베시는 이미 지어진 $M$개의 길을 그것을 지은 농장에 배정하는 서로 다른 방법이 몇 가지인지 알고 싶어 합니다. 예를 들어 어떤 길이 농장 $3$과 $4$를 잇는다면, 농장 $3$이 지었을 수도 있고 농장 $4$가 지었을 수도 있습니다. 어떤 길을 지은 농장이 하나라도 다르면 두 방법은 서로 다른 것으로 봅니다.

배정하는 방법의 수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력하세요. 유효한 배정이 하나도 없으면 $0$을 출력합니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$째 줄까지: $i+1$째 줄은 $i$번째 길을 나타내며, 공백으로 구분된 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$)로 그 길이 잇는 두 농장을 나타냅니다.

• 한 줄에 정수 하나: 길을 지은 농장에 배정하는 방법의 수를 $1{,}000{,}000{,}007$로 나눈 나머지. 유효한 배정이 없으면 $0$을 출력합니다.

같은 두 농장을 잇는 길이 두 개 이상 있을 수도 있습니다.