#include <stdio.h>

using namespace std;

int main()
{
    freopen ("grid.in", "r", stdin);
    freopen ("grid.out", "w" , stdout);
    int n, k, blocked[3][2];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; i++)
    {
        scanf("%d %d", &blocked[i][0], &blocked[i][1]);
        blocked[i][0]--;
        blocked[i][1]--;
    }
    //printf("before matrix definition\n");
    long long matrix[n][n];
    for (int i = 1; i < n; i++) matrix[0][i] = matrix[i][0] = 1;
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
        {
            matrix[i][j] = matrix[i - 1][j] + matrix[i][j-1];
            if (matrix[i][j] > 10000000019) matrix[i][j] %= 10000000019;
            for (int q = 0; q < k; q++)
                if ((i == blocked[q][0]) && (j == blocked[q][1]))
                {
                    matrix[i][j] = 0;
                    q = k;
                }
        }
    printf("%lld\n", (matrix[n - 1][n - 1] % 10000000019));
    fclose(stdin);
    fclose(stdout);
    return 0;
}