Päiväkodissa on n lasta ja n lelua. Jokainen lelu voi olla kerrallaan yhdellä lapsella, ja jokainen lapsi haluaa leikkiä. Lisäksi kukin lapsi kelpuuttaa vain tietyt lelut. Kuinka monella tavalla lelut voidaan jakaa lapsille niin, että kaikki ovat tyytyväisiä? Tulosta ratkaisu modulo 10^9+7.

Syöte

Ensimmäisellä rivillä kaksi kokonaislukua n ja m: lelujen sekä kelvollisten lapsi–lelu-parien määrä.

Seuraavat m riviä sisältävät kaksi lukua x ja y, jotka kertovat lapsen x hyväksyvän lelun y.

Tuloste

Kelvollisten lelujakojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 20
• 0 \le m \le n^2

Esimerkki

Syöte:

3 5
1 1
2 2
2 3
3 2
3 3

Tuloste:

2