Simulare Lot 2018 Baraj 4 Juniori | berze

E primavară şi se întorc berzele. În satul nostru, stâlpii de la marginea drumului au vârfurile prea ascuţite şi din această cauză berzele nu-şi pot face cuib. Aşa că e tristeţe mare la noi $\dots$ Dar ne-am adunat cu toţii şi am hotărât ca pe vârful unor stâlpi să instalăm câte un suport orizontal plan, astfel încât să nu-i fie greu unei berze să-şi amenajeze cuibul. Avem $n$ stâlpi la marginea drumului, dispuşi liniar şi numerotaţi de la $0$ la $n - 1$.

Un număr de $m$ săteni au venit cu câte o restricţie de forma $i \ j$, însemnând faptul că pe stalpii din intervalul $[i, j]$ se pot instala cel mult două suporturi pentru cuiburi de berze. Motivele acestor restricţii sunt diverse, cum ar fi de pildă apropierea prea mare între anumiţi stâlpi. Vom ţine seama de ele pentru că vrem ca toţi sătenii să fie mulţumiţi.

Cerinţă

Cunoscând $n$, $m$ şi cele $m$ restricţii să se determine numărul de posibilităţi ca berzele să-şi amenajeze cuiburi pe cei $n$ stâlpi, modulo $700 \ 001$.

Date de intrare

Fişierul de intrare berze.in conține pe prima linie numerele $n$ şi $m$ având semnificaţia din enunţ. Pe următoarele $m$ linii se găsesc câte două numere naturale $i$, $j$, reprezentând faptul că în intervalul de stâlpi $[i, i+1, i+2, \dots, j]$ se pot amenaja cel mult două suporturi pentru cuiburi de berze.

Date de ieșire

Fişierul de ieșire berze.out va conţine pe o singură linie un număr natural ce reprezintă numărul de posibilităţi de a plasa suporturi pentru cuiburi de berze pe cei $n$ stâlpi.

Restricții și precizări

• $2 \leq m, n \leq 1 \ 000$
• $0 \leq i < j \leq n - 1$
• cele $m$ intervale de forma $i \ j$ nu sunt neapărat disjuncte
• pe un stâlp se poate instala cel mult un suport pentru cuib de barză
• pentru $50\%$ din teste $N \leq 100$

Exemplu

berze.in

4 1
0 2

berze.out

14

Explicație

Notăm cu I un stâlp fără suport pentru cuib de barză şi cu T un stâlp cu suport. Atunci cele $14$ soluţii sunt:

I I I I 
I I I T
T I I I 
T I I T
I T I I 
I T I T
I I T I 
I I T T
T T I I 
T T I T
T I T I 
T I T T
I T T I 
I T T T