Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Lentoreitti

Lentoreitti


View task | Model solution | Statistics


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
Esimerkki

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


Tuloste:
2