trasee

Elena a desenat pe hârtie vârfurile unui poligon regulat și le-a numerotat cu $1$, $2$, $3$, $\dots$, $N$ în sensul acelor de ceasornic. Ea vrea să deseneze, fără să ridice creionul de pe hârtie, fiecare traseu posibil care pornește din vârful $1$ și trece prin fiecare vârf al poligonului câte o singură dată. Traseele pot parcurge atât muchiile cât și diagonalele poligonului, dar trebuie astfel desenate încât să nu se autointersecteze. În plus Elena își alege $M$ diagonale care nu trebuie trasate cu creionul pe niciunul dintre trasee.

Cerință

Să se afle numărul $X$ al traseelor ce pot fi construite.

Date de intrare

Fișierul de intrare trasee.in conține pe prima linie numerele $N$ și $M$, iar pe următoarele $M$ linii câte două numere, reprezentând vârfurile între care se găsesc diagonalele ce nu trebuie trasate.

Date de ieșire

În fișierul de ieșire trasee.out se va scrie numărul obținut ca rest la împărțirea dintre numărul $X$ al traseelor și numărul $1 \ 000 \ 000 \ 007$

Restricții și precizări

• $3 \leq N \leq 1 \ 000$
• $0 \leq M \leq N$

Exemplul 1

trasee.in

3 0

trasee.out

2

Explicație

Traseele posibile sunt $1, 2, 3$ si $1, 3, 2$

Exemplul 2

trasee.in

5 2
1 3
2 5

trasee.out

4

Explicație

Nu trebuie trasate diagonalele $1, 3$ și $2, 5$.

Traseele posibile sunt $1, 2, 3, 4, 5$; $1, 2, 3, 5, 4$; $1, 5, 4, 2, 3$; $1, 5, 4, 3, 2$;