#include <iostream>
#include <stdio.h>
using namespace std;
#define MOD 10000000019LL
typedef long long Int;

Int F[2][6003];
int n;
int k;
bool Unused[6003][6003];

int main()
{
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);

    int i,j;
    int x,y;
    int cur,op;

    scanf("%d %d",&n,&k);

    for (i=1;i<=k;i++)
    {
        scanf("%d %d",&x,&y);
        Unused[x][y]=true;
    }

    if (Unused[n][n] || Unused[1][1])
    {
        printf("0\n");
        return 0;
    }

    for (i=n;i>=1;i--)
    {
        cur=i%2;
        op=cur^1;

        for (j=n;j>=1;j--)
        {
            if (i==n && j==n)
            {
                F[cur][j]=1;
                continue;
            }
            if (Unused[i][j])
            {
                F[cur][j]=0;
                continue;
            }

            F[cur][j]=F[op][j]+F[cur][j+1];
            if (F[cur][j]>=MOD)
            F[cur][j]-=MOD;
        }
    }

    printf("%lld\n",F[cur][1]);

    return 0;
}