lostarray

Enunț

Chertes are un vector $v$ cu $n$ numere naturale. Acest vector este foarte valoros pentru personajul nostru, așa că el își dorește să salveze informații despre vector astfel încât să-l poată reconstrui, în cazul în care îl pierde. O informație reprezintă o pereche de numere naturale $(x,y) (1 \leq x \leq y \leq n)$, care are următoarea semnificație: se salvează suma elementelor din secvența $v[x..y]$. Formal, se salvează suma elementelor $v_x, v_{x+1}, ... v_{y}$.
Spre exemplu, dacă avem vectorul $v=[1,2,7,3,8]$, o informație validă ar putea fi $(1,3)$ (se salvează suma elementelor $1$, $2$ și $7$, care este $10$). În schimb, informația $(2,1)$ nu este validă deoarece $2=x>y=1$.

Cerință

Deoarece Chertes este un băiat leneș, dar isteț, vă pune următoarea întrebare: în câte moduri putem salva un număr minim de informații, astfel încât să putem reconstrui vectorul? Mai grav! Acesta restrictioneaza salvarea unor informații. Mai exact se dau $m$ perechi $(x,y)$ ce reprezintă informațiile pe care nu le poți salva, cu alte cuvinte nu poți salva suma elementelor din secvență $v[x..y]$. Și mai grav!! Numărul de moduri este foarte mare asfel se cere restul împărțirii lui la $10^9 + 7$.
Două moduri sunt diferite dacă unul dintre ele conține cel puțin o informație diferită față de cealălalt.

Date de intrare

Fișierul de intrare lostarray.in conține pe prima linie un număr natural $n$ reprezentând numărul de elemente ale vectorului. Pe a doua linie se afla un număr natural $m$ reprezentând numărul de restricții. Pe următoarele $m$ linii se vor afla perechi de tipul $(x,y)$ reprezentând faptul că nu poți salva informația $(x,y)$.

Date de ieșire

Fișireul de ieșire lostarray.out conține pe prima linie numărul $k$ reprezentând numarul de moduri modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq n \leq 500$
• $0 \leq m \leq \frac{n \times (n + 1)}{2}$
• Pentru teste în valoare de $60p$ avem $m = 0$

Exemplu

lostarray.in

2
0

lostarray.out

3

Explicații

Sunt 3 moduri de a salva un număr minim de informații astfel incât putem reconstrui vectorul: $[(1,1), (2, 2)]$, $[(1,1), (1, 2)]$ și $[(1,2), (2, 2)]$.