#include<iostream>
#include<cstdio>
const int x = 0, y = 1;
using namespace std;
int main()
{
	freopen ("board.in", "r", stdin);
	freopen ("board.out", "w" , stdout);
	int n,k;
	cin >> n >> k;

	int x1 = 70000, y1 = 70000, x2 = 70000, y2 = 70000;
	if(k){cin >> x1 >> y1; x1--;}
	if(k == 2){cin >> x2 >> y2; x2--;}
	long long *upper;
	upper = new long long[n+1];
	upper[0] = 1;
	for(int i = 1; i <= n; ++i)
	{
		upper[i] = upper[i-1];
		if(x1==0 && y2==i)upper[i] = 0;
		if(x2==0 && y2==i)upper[i] = 0;
	}
	for(int i = 1; i < n; ++i)
	{
		long long *lower;
		lower = new long long [n+1];
		lower[0] = 0;
		for(int j = 1; j <= n; ++j)
		{
			lower[j] = upper[j];
			lower[j] += lower[j - 1];
			lower[j] %= 10000000019;
			if(x1 == i && y1 == j)lower[j]=0;
			if(x2 == i && y2 == j)lower[j]=0;
		}
		upper = lower;
		delete[] lower;
	}
	cout << upper[n]<<endl;
	return 0;

}