Fie $G$ un graf **orientat aciclic** fără costuri pe muchii. În această problemă vom analiza ce se întâmplă dacă folosim o pargurgere în adâncime pentru a calcula drumul de lungime minimă dintre nodul **$1$** şi nodul **$N$**. Mai exact, vom rula algoritmul descris de următoarea secvenţă de pseudocod:

== code(python) |

== code(cpp) |

viz[x] = 0, oricare ar fi x
dist[1] = 0

Formarea listelor de adiacenţă ale grafului urmează următorul pseudocod (unde $lista[x]$ reprezintă lista vecinilor lui $x$):

== code(python) |

== code(cpp) |

lista[x] = [], oricare ar fi x
citeste n, m

h2. Date de ieşire

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 **$1000000007$**.

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