afişează dist[N]
==

Formarea listelor de adiacenţă ale grafului urmează următorul pseudocod ( unde lista[x] reprezintă lista vecinilor lui x) :
 
== code(cpp) |
lista[x] = [], oricare ar fi x
 
citeste n, m
pentru i de la 1 la m:
   citeste a, b
   adauga b la sfarsitul lui lista[a]
==
 
Bineînţeles, acest algoritm nu este întotdeauna corect, deoarece distanţa calculată depinde de ordinea în care sunt procesaţi vecinii unui nod în timpul citirii.
De exemplu, dacă la construirea grafului se citeşte întâi muchia (1 → 2) şi apoi muchia (1 → 3), atunci când vecinii lui 1 sunt prelucraţi, primul vecin va fi 2, iar următorul va fi 3.Aşadar, distanţa calculată cu primul algoritm de mai sus poate fi diferită, în funcţie de ordinea în care sunt adăugate muchiile de la citire. Prin urmare, pentru un graf dat, suntem curioşi pentru câte dintre cele M! permutări ale muchilor lui G, algoritmul DFS va da distanţa minimă.
 

h2. Date de intrare

Fişierul de intrare $shuffle2.in$ ...

Pe prima linie a fişierului de intrare $shuffle2.in$ se vor afla două numere naturale **$N$**, numărul de noduri, şi
**$M$**, numărul de muchii. Pe următoarele **$M$** linii se vor afla două numere **$x$** si **$y$**, reprezentând faptul că în graf
există muchia orientată de la **$x$** la **$y$**.

h2. Date de ieşire

În fişierul de ieşire $shuffle2.out$ ...

Pe prima linie a fişierului de ieşire $shuffle2.out$ se va afişa un singur număr, care reprezintă numărul de permutări acceptabile modulo **$1 000 000 007$**.

h2. Restricţii