Bessie y las vacas vecinas decidieron conectar sus granjas con senderos para aliarse contra los granjeros. Cada una de las $N$ granjas ($1 \le N \le 100,000$) debía construir un sendero a exactamente otra, para un total de $N$. Tras meses solo se construyeron $M$ ($1 \le M < N$).

Las discusiones sobre qué granjas ya construyeron amenazan la alianza. Bessie quiere contar las formas de construir los $M$ senderos existentes para reducir tensiones. Uno entre 3 y 4 pudo construirlo la granja 3 o la 4. Cuenta las asignaciones de senderos a su granja constructora módulo 1,000,000,007. Son distintas si al menos un sendero tiene constructora diferente.

Entrada

• Línea 1: los enteros $N$ y $M$ separados por un espacio.
• Líneas $2..1+M$: la línea $i+1$ describe el sendero $i$ con $u_{i}$ y $v_{i}$ separados por un espacio ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), las granjas conectadas.

Salida

• Línea 1: el número de asignaciones módulo 1,000,000,007. Si ninguna cumple las condiciones, imprime 0.

Ejemplos

Entrada 1

5 4
1 2
3 2
4 5
4 5

Salida 1

6

Nota

Puede haber dos senderos entre la misma pareja de granjas.

Hay 6 asignaciones. $\{a,b,c,d\}$ significa que la granja 1 construye el sendero a, la 2 el b, la 3 el c y la 4 el d. Las asignaciones son: $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Autor: Mark Gordon, 2011