CSES - Lentoreitti
  • Time limit: 1.00 s
  • Memory limit: 128 MB
Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ lentoyhteyttä. Haluat lentää Syrjälästä Lehmälään niin, että käyt reitin aikana tasan kerran jokaisessa kaupungissa. Monellako tavalla voit valita reitin?

Syöte

Syötteessä on ensin kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu $1,2,\ldots,n$. Kaupunki 1 on Syrjälä ja kaupunki $n$ on Lehmälä.

Sitten syötteessä on $m$ riviä, jotka kuvaavat lentoyhteydet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: mistä yhteys alkaa ja mihin se päätyy. Kaikki yhteydet ovat yksisuuntaisia.

Tuloste

Tulosta yksi kokonaisluku: reittien määrä modulo $10^9+7$.

Rajat
  • $2 \le n \le 20$
  • $1 \le m \le n^2$
  • $1 \le a,b \le n$
Esimerkki

Syöte:
4 6
1 2
1 3
2 3
3 2
2 4
3 4


Tuloste:
2