/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;
FILE *in; FILE *out;

const int MAX = 6006;
const long long MOD = 10000000019LL;

int n, m, k;
bool bad[MAX][MAX];
long long ans[2][MAX];

long long eval() {
    memset(ans, 0, sizeof(ans));
    int cur = 0;
    for (int row = n - 1; row >= 0; row--) {
        cur = !cur;
        if (row == n - 1) {
            if (!bad[n - 1][m - 1])
                ans[cur][m - 1] = 1;
        } else {
            ans[cur][m - 1] = ans[!cur][m - 1];
        }
        
        for (int col = m - 2; col >= 0; col--) {
            ans[cur][col] = 0;
            if (!bad[row][col]) {
                if (row + 1 < n) {
                    ans[cur][col] += ans[!cur][col];
                    if (ans[cur][col] >= MOD)
                        ans[cur][col] -= MOD;
                }
                if (col + 1 < m) {
                    ans[cur][col] += ans[cur][col + 1];
                    if (ans[cur][col] >= MOD)
                        ans[cur][col] -= MOD;
                }
            }
        }
    }
    return ans[cur][0];
}

string toString(long long num) {
    if (num == 0)
        return "0";
    string sign = "";
    if (num < 0)
        sign = "-", num = -num;
    
    string ret;
    while (num)
        ret += (num % 10 + '0'), num /= 10;
    reverse(ret.begin(), ret.end());
    return sign + ret;
}

int main(void) {
	in = stdin; out = stdout;
	in = fopen("grid.in", "rt"); out = fopen("grid.out", "wt");
	
	fscanf(in, "%d %d", &n, &k); m = n;
	for (int i = 0; i < k; i++) {
	    int row, col;
	    fscanf(in, "%d %d", &row, &col);
	    row--, col--;
	    bad[row][col] = true;
	}
	
	fprintf(out, "%s\n", toString(eval()).c_str());
	return 0;
}