Bessie et les vaches voisines ont décidé de relier leurs fermes par des sentiers pour s’allier contre les fermiers. Chacune des $N$ fermes ($1 \le N \le 100,000$) devait construire un sentier vers exactement une autre, soit $N$ sentiers. Après des mois, seuls $M$ sont construits ($1 \le M < N$).

Les disputes sur les fermes ayant déjà construit un sentier menacent l’alliance. Bessie veut compter les façons de construire les $M$ sentiers existants pour apaiser les tensions. Un sentier entre 3 et 4 peut avoir été construit par la ferme 3 ou la ferme 4. Comptez les attributions des sentiers à leur ferme constructrice modulo 1,000,000,007. Deux attributions diffèrent si au moins un sentier a des constructeurs différents.

Entrée

• Ligne 1 : les entiers $N$ et $M$ séparés par un espace.
• Lignes $2..1+M$ : la ligne $i+1$ décrit le sentier $i$ avec $u_{i}$ et $v_{i}$ séparés par un espace ($1 \le u_{i}, v_{i} \le N, u_{i} \ne v_{i}$), les fermes reliées.

Sortie

• Ligne 1 : le nombre d’attributions modulo 1,000,000,007. Si aucune ne respecte les conditions, affichez 0.

Exemples

Entrée 1

5 4
1 2
3 2
4 5
4 5

Sortie 1

6

Remarque

Deux sentiers peuvent relier la même paire de fermes.

Il y a 6 attributions. $\{a,b,c,d\}$ signifie que la ferme 1 construit le sentier a, la ferme 2 le b, la 3 le c et la 4 le d. Les attributions sont : $\{2, 3, 4, 5\}$ $\{2, 3, 5, 4\}$ $\{1, 3, 4, 5\}$ $\{1, 3, 5, 4\}$ $\{1, 2, 4, 5\}$ $\{1, 2, 5, 4\}$

Auteur : Mark Gordon, 2011