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