• 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