#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define MOD 1000000009
#define NUM 1005
#define MAX 2000005
#define DIFF 20

struct Info{
	bool operator<(const struct Info &arg) const{
		if(ROW+COL != arg.ROW+arg.COL){
			return ROW+COL < arg.ROW+arg.COL;
		}else{
			if(COL != arg.COL){
				return COL < arg.COL;
			}else{
				return ROW < arg.ROW;
			}

		}
	}
	Info(){
		ROW = COL = 0;
	}
	Info(ll arg_ROW,ll arg_COL){
		ROW = arg_ROW;
		COL = arg_COL;
	}
	ll ROW,COL;
};

struct State{
	State(ll arg_row,ll arg_col,ll arg_sum_dist){
		row = arg_row;
		col = arg_col;
		sum_dist = arg_sum_dist;
	}
	bool operator<(const struct State &arg) const{
		return sum_dist > arg.sum_dist;
	}
	ll row,col;
	ll sum_dist;
};

ll N,M;
ll fact[MAX];
ll min_dist[NUM][NUM];
ll dp[NUM][NUM],dp2[NUM][NUM],dp3[55][55];
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
bool check[NUM][NUM],is_shortest[NUM][NUM],is_shortest2[NUM][NUM];
Info info[55];


ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}

ll nCm(ll n,ll m,ll p){
   if(n < m) return 0;
   ll e1,e2,e3;
   ll a1 = mod_fact(n,p,e1),a2 = mod_fact(m,p,e2),a3 = mod_fact(n-m,p,e3);
   if(e1 > e2+e3)return 0;
   return a1 * mod_inverse(a2*a3%p,p)%p;
}

bool rangeCheck(ll row,ll col){

	return row >= 0 && row <= N-1 && col >= 0 && col <= N-1;
}

ll calc(ll base_row,ll base_col){

	vector<Info> V;
	V.push_back(Info(base_row,base_col));

	for(int i = 0; i < M; i++){
		V.push_back(info[i]);
	}

	sort(V.begin()+1,V.begin()+1+M);

	ll ret = 0;

	for(int i = 0; i <= M; i++){
		for(int k = 0; k <= M; k++){
			dp3[i][k] = 0;
		}
	}

	dp3[0][0] = 1;
	ll diff_ROW,diff_COL;

	for(int i = 0; i <= M; i++){
		for(int num = 0; num <= i; num++){
			if(dp3[i][num] == 0)continue;

			for(int col = 0; col <= M+DIFF; col++){
				if(!is_shortest2[M+DIFF-col][col])continue;

				diff_ROW = (N-1)-(M+DIFF-col)-V[i].ROW;
				diff_COL = (N-1)-col-V[i].COL;

				if(num%2 == 0){ //偶数なら足す
					ret += (((nCm(diff_ROW+diff_COL,diff_ROW,MOD)*dp3[i][num]%MOD)%MOD)*dp2[M+DIFF-col][col]%MOD)%MOD;
					ret %= MOD;

				}else{ //奇数なら引く
					ret -=  (((nCm(diff_ROW+diff_COL,diff_ROW,MOD)*dp3[i][num]%MOD)%MOD)*dp2[M+DIFF-col][col]%MOD)%MOD;
					ret %= MOD;
					if(ret < 0)ret += MOD;
				}
			}

			for(int next = i+1; next <= M; next++){

				diff_ROW = V[next].ROW-V[i].ROW;
				diff_COL = V[next].COL-V[i].COL;

				if(diff_ROW < 0 || diff_COL < 0)continue;

				dp3[next][num+1] += dp3[i][num]*nCm(diff_ROW+diff_COL,diff_ROW,MOD)%MOD;
				dp3[next][num+1] %= MOD;
			}
		}
	}

    return ret;
}

void func_BIG(){

	if(M == 0){
		printf("%lld\n",nCm(2*(N-1),N-1,MOD));
		return;
	}

	for(int row = 0; row < M+DIFF+10; row++){
		for(int col = 0; col < M+DIFF+10; col++){
			min_dist[row][col] = BIG_NUM;
			dp[row][col] = 0;
			check[row][col] = false;
			is_shortest[row][col] = false;
		}
	}

	for(int i = 0; i < M; i++){
		if(info[i].ROW < M+DIFF+10 && info[i].COL < M+DIFF+10){

			check[info[i].ROW][info[i].COL] = true;
		}
	}

	priority_queue<State> Q;
	min_dist[0][0] = 0;
	dp[0][0] = 1;
	Q.push(State(0,0,0));

	ll adj_row,adj_col,next_cost;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().row][Q.top().col]){

			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){

				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(adj_row == M+DIFF+10 || adj_col == M+DIFF+10)continue;
				if(rangeCheck(adj_row,adj_col) == false || check[adj_row][adj_col] == true)continue;

				next_cost = Q.top().sum_dist+1;

				if(min_dist[adj_row][adj_col] > next_cost){

					min_dist[adj_row][adj_col] = next_cost;
					dp[adj_row][adj_col] += dp[Q.top().row][Q.top().col];

					Q.push(State(adj_row,adj_col,next_cost));

				}else if(min_dist[adj_row][adj_col] == next_cost){

					dp[adj_row][adj_col] += dp[Q.top().row][Q.top().col];
					dp[adj_row][adj_col] %= MOD;
				}
			}

			Q.pop();
		}
	}

	ll minimum = BIG_NUM;
	for(int col = 0; col <= M+DIFF; col++){

		if(min_dist[M+DIFF-col][col] == BIG_NUM)continue;
		minimum = min(minimum,min_dist[M+DIFF-col][col]);
	}

	for(int col = 0; col <= M+DIFF; col++){

		if(min_dist[M+DIFF-col][col] == minimum){
			is_shortest[M+DIFF-col][col] = true;
		}
	}


	for(int row = 0; row < M+DIFF+10; row++){
		for(int col = 0; col < M+DIFF+10; col++){
			min_dist[row][col] = BIG_NUM;
			check[row][col] = false;
			dp2[row][col] = 0;
			is_shortest2[row][col] = false;
		}
	}

	for(int i = 0;i < M; i++){
		if(info[i].ROW >= N-(M-(DIFF+10)) && info[i].COL >= N-(M-(DIFF+10))){
			check[N-1-info[i].ROW][N-1-info[i].COL] = true;
		}
	}

	dp2[0][0] = 1;
	min_dist[0][0] = 0;
	Q.push(State(0,0,0));

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().row][Q.top().col]){

			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){

				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(adj_row == M+DIFF+10 || adj_col == M+DIFF+10)continue;
				if(rangeCheck(adj_row,adj_col) == false || check[adj_row][adj_col] == true)continue;

				next_cost = Q.top().sum_dist+1;

				if(min_dist[adj_row][adj_col] > next_cost){

					min_dist[adj_row][adj_col] = next_cost;
					dp2[adj_row][adj_col] += dp2[Q.top().row][Q.top().col];

					Q.push(State(adj_row,adj_col,next_cost));

				}else if(min_dist[adj_row][adj_col] == next_cost){

					dp2[adj_row][adj_col] += dp2[Q.top().row][Q.top().col];
					dp2[adj_row][adj_col] %= MOD;
				}
			}
			Q.pop();
		}
	}

	minimum = BIG_NUM;
	for(int col = 0; col <= M+DIFF; col++){

		if(min_dist[M+DIFF-col][col] == BIG_NUM)continue;
		minimum = min(minimum,min_dist[M+DIFF-col][col]);
	}

	for(int col = 0; col <= M+DIFF; col++){

		if(min_dist[M+DIFF-col][col] == minimum){
			is_shortest2[M+DIFF-col][col] = true;
		}
	}

	ll ans = 0;

	for(int col = 0; col <= M+DIFF; col++){
		if(is_shortest[M+DIFF-col][col]){

			ans += calc(M+DIFF-col,col)*dp[M+DIFF-col][col]%MOD;
			ans %= MOD;
		}
	}
	printf("%lld\n",ans);
}

void func_SMALL(){

	for(int row = 0; row < N; row++){
		for(int col = 0; col < N; col++){
			min_dist[row][col] = BIG_NUM;
			dp[row][col] = 0;
			check[row][col] = false;
		}
	}

	for(int i = 0; i < M; i++){
		check[info[i].ROW][info[i].COL] = true;
	}

	priority_queue<State> Q;
	min_dist[0][0] = 0;
	dp[0][0] = 1;
	Q.push(State(0,0,0));

	ll adj_row,adj_col,next_cost;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_dist[Q.top().row][Q.top().col]){

			Q.pop();
		}else{

			for(int i = 0; i < 4; i++){

				adj_row = Q.top().row+diff_row[i];
				adj_col = Q.top().col+diff_col[i];

				if(rangeCheck(adj_row,adj_col) == false || check[adj_row][adj_col] == true)continue;

				next_cost = Q.top().sum_dist+1;

				if(min_dist[adj_row][adj_col] > next_cost){

					min_dist[adj_row][adj_col] = next_cost;
					dp[adj_row][adj_col] = dp[Q.top().row][Q.top().col];

					Q.push(State(adj_row,adj_col,next_cost));

				}else if(min_dist[adj_row][adj_col] == next_cost){

					dp[adj_row][adj_col] += dp[Q.top().row][Q.top().col];
					dp[adj_row][adj_col] %= MOD;
				}
			}

			Q.pop();
		}
	}

	printf("%lld\n",dp[N-1][N-1]);
}

int main(){

	fact[0] = 1;
	for(ll i = 1;i < MAX; i++){
		fact[i] = fact[i-1]*i%MOD;
	}

	scanf("%lld %lld",&N,&M);

	for(int i = 0; i < M; i++){

		scanf("%lld %lld",&info[i].COL,&info[i].ROW);

		info[i].COL--;
		info[i].ROW--;
	}

	if(N <= 1000){

		func_SMALL();

	}else{

		func_BIG();
	}

	return 0;
}



Measured memory_bytes: 35572