E primăvară ș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… 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 stâlpii 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ța

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 700001.

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,...,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 ≤ m, n ≤ 1000
• 0 ≤ i < j ≤ 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 ≤ 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
T I I I
I T I I
I I T I
T T I I
T I T I
I T T I
I I I T
T I I T
I T I T
I I T T
T T I T
T I T T
I T T T
Observați că restricția este între stâlpii 0 și 2.

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("berze.in");
ofstream fout ("berze.out");

#define MAX 1001
#define MOD 700001

int n, m, nxt[MAX];
int A[MAX][MAX];

int main()
{
    fin >> n >> m;
    for (int i = 1, x, y; i <= m; i ++)
    {
        fin >> x >> y;
        nxt[x] = max(nxt[x], y + 1);
    }

    for (int i = 1; i <= n; i ++)
        nxt[i] = max(nxt[i], nxt[i - 1]);

    A[0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
        {
            if (!A[i - 1][j]) continue;

            A[i][j] += A[i - 1][j];
            A[i][j] %= MOD;

            if (j <= i)
            {
                A[i][nxt[i - 1]] += A[i - 1][j];
                A[i][nxt[i - 1]] %= MOD;
            }
            else
            {
                A[j][nxt[i - 1]] += A[i - 1][j];
                A[j][nxt[i - 1]] %= MOD;
            }
        }

    int rez = 0;
    for (int i = 0; i <= n; ++i)
    {
        rez += A[n][i];
        rez %= MOD;
    }
    fout << rez;
    return 0;
}