#include <bits/stdc++.h>
#define MOD 1000000009LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int n,m;
int x[51],y[51];
int dist[1005][1005];
ll dp2[1005][1005];
int dist2[1005][1005];
ll dp3[1005][1005];
P pos[55];
vector<int> vx;
vector<int> vy; 
ll dp[1005][1005];
ll fact[2000005];
bool ok[2][305];

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0LL){
		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;
	ll 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 mod_comb(ll n,ll k,ll p){
	if(n<0 || k<0 || n<k)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
	if(e1>e2+e3)return 0;
	return a1*mod_inverse(a2*a3%p,p)%p;
}


ll calcdp(int sy,int sx){
	for(int i=0;i<m;i++){
		pos[i+1]=P(y[i],x[i]);
	}
	memset(dp,0,sizeof(dp));
	pos[0]=P(sy,sx);
	sort(pos+1,pos+m+1);
	dp[0][0]=1;
	ll ans=0;
	for(int i=0;i<m+1;i++){
		for(int j=0;j<=i;j++){
			if(dp[i][j]==0)continue;
			for(int k=0;k<=m+20;k++){
				if(ok[1][k]){
					int dx=n-1-k-pos[i].second;
					int dy=n-1-(m+20-k)-pos[i].first;
					if(dx<0 || dy<0)continue;
					if(j%2==0){
						ans+=(mod_comb(dx+dy,dx,MOD)*dp[i][j]%MOD)*dp3[m+20-k][k]%MOD;
						ans%=MOD;
					}
					if(j%2==1){
						ans-=(mod_comb(dx+dy,dx,MOD)*dp[i][j]%MOD)*dp3[m+20-k][k]%MOD;;
						ans%=MOD;
						if(ans<0LL){
							ans+=MOD;
						}
					}
				}
			}
			
			for(int k=i+1;k<m+1;k++){
				int d1=pos[k].first-pos[i].first;
				int d2=pos[k].second-pos[i].second;
				if(d1>=0 && d2>=0){
					dp[k][j+1]+=dp[i][j]*mod_comb(d1+d2,d1,MOD)%MOD;
					dp[k][j+1]%=MOD;
				}
			}
		}
	}
	return ans;
}

ll calc(){
	memset(dist,-1,sizeof(dist));
	queue<P> que;
	for(int i=0;i<m;i++){
		if(y[i]<m+30 && x[i]<m+30)dist[y[i]][x[i]]--;
	}
	que.push(P(0,0));
	dist[0][0]=0;
	dp2[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=m+30 || ny<0 || ny>=m+30)continue;
			if(dist[ny][nx]==-1){
				dist[ny][nx]=dist[p.first][p.second]+1;
				dp2[ny][nx]+=dp2[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist[ny][nx]==dist[p.first][p.second]+1){
				dp2[ny][nx]+=dp2[p.first][p.second];
				dp2[ny][nx]%=MOD;
			}
		}
	}

	memset(dist2,-1,sizeof(dist2));
	for(int i=0;i<m;i++){
		if(y[i]>=n-(m-30) && x[i]>=n-(m-30))dist2[n-1-y[i]][n-1-x[i]]--;
	}
	que.push(P(0,0));
	dist2[0][0]=0;
	dp3[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=m+30 || ny<0 || ny>=m+30)continue;
			if(dist2[ny][nx]==-1){
				dist2[ny][nx]=dist2[p.first][p.second]+1;
				dp3[ny][nx]+=dp3[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist2[ny][nx]==dist2[p.first][p.second]+1){
				dp3[ny][nx]+=dp3[p.first][p.second];
				dp3[ny][nx]%=MOD;
			}
		}
	}
	int d_min=1LL<<30;
	for(int i=0;i<=m+20;i++){
		if(dist[m+20-i][i]>=0)d_min=min(d_min,dist[m+20-i][i]);
	}
	for(int i=0;i<=m+20;i++){
		if(d_min==dist[m+20-i][i]){
			ok[0][i]=true;
		}
	}
	d_min=1LL<<30;
	for(int i=0;i<=m+20;i++){
		if(dist2[m+20-i][i]>=0)d_min=min(d_min,dist2[m+20-i][i]);
	}
	for(int i=0;i<=m+20;i++){
		if(d_min==dist2[m+20-i][i]){
			ok[1][i]=true;
		}
	}
	ll ans=0;
	for(int i=0;i<=m+20;i++){
		if(ok[0][i]){
			ans+=calcdp(m+20-i,i)*dp2[m+20-i][i]%MOD;
			ans%=MOD;
		}
	}
	return ans;
}

ll bfs(){
	memset(dist,-1,sizeof(dist));
	queue<P> que;
	for(int i=0;i<m;i++){
		dist[y[i]][x[i]]--;
	}
	que.push(P(0,0));
	dist[0][0]=0;
	dp2[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=n || ny<0 || ny>=n)continue;
			if(dist[ny][nx]==-1){
				dist[ny][nx]=dist[p.first][p.second]+1;
				dp2[ny][nx]+=dp2[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist[ny][nx]==dist[p.first][p.second]+1){
				dp2[ny][nx]+=dp2[p.first][p.second];
				dp2[ny][nx]%=MOD;
			}
		}
	}
	return dp2[n-1][n-1];
}


int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x[i],&y[i]);
		x[i]--;
		y[i]--;
	}
	if(n>=1000){
		fact[0]=1;
		for(int i=1;i<=n*2;i++){
			fact[i]=(ll)fact[i-1]*i%MOD;
		}
		printf("%lld\n",calc());
	}else{
		printf("%lld\n",bfs());
	}
	return 0;
} 

### Prompt

Your task is to create a Cpp solution to the following problem:

There is an NxN grid.

<image>
(Figure when N = 3)

It costs 1 to move to an adjacent square. However, it cannot be moved diagonally. Also, there are M squares with obstacles, and you are not allowed to enter those squares. How many ways are there to move from mass (1, 1) to mass (N, N) at the lowest cost? The answer can be big, so take the mod at 1000000009 (= 109 + 9) and output it.

Constraints

* 2 ≤ N ≤ 106

* 0 ≤ M ≤ 50

* 1 ≤ Xi, Yi ≤ N

* If i ≠ j, then (Xi, Yi) ≠ (Xj, Yj)

* (Xi, Yi) ≠ (1, 1)

* (Xi, Yi) ≠ (N, N)

Input

Input is given in the following format

> N M
> X1 Y1
> X2 Y2
> ……
> XM YM
>

Xi, Yi means that there is an obstacle in (Xi, Yi)

Output

Output the total number of routes on one line. However, if there is no route to move from the mass (1, 1) to the mass (N, N), output 0.

Examples

Input

3 0


Output

6


Input

3 1
2 2


Output

2


Input

5 8
4 3
2 1
4 2
4 4
3 4
2 2
2 4
1 4


Output

1


Input

1000 10
104 87
637 366
393 681
215 604
707 876
943 414
95 327
93 415
663 596
661 842


Output

340340391


Input

2 2
1 2
2 1


Output

0

### Response

```cpp
#include <bits/stdc++.h>
#define MOD 1000000009LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int n,m;
int x[51],y[51];
int dist[1005][1005];
ll dp2[1005][1005];
int dist2[1005][1005];
ll dp3[1005][1005];
P pos[55];
vector<int> vx;
vector<int> vy; 
ll dp[1005][1005];
ll fact[2000005];
bool ok[2][305];

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0LL){
		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;
	ll 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 mod_comb(ll n,ll k,ll p){
	if(n<0 || k<0 || n<k)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
	if(e1>e2+e3)return 0;
	return a1*mod_inverse(a2*a3%p,p)%p;
}


ll calcdp(int sy,int sx){
	for(int i=0;i<m;i++){
		pos[i+1]=P(y[i],x[i]);
	}
	memset(dp,0,sizeof(dp));
	pos[0]=P(sy,sx);
	sort(pos+1,pos+m+1);
	dp[0][0]=1;
	ll ans=0;
	for(int i=0;i<m+1;i++){
		for(int j=0;j<=i;j++){
			if(dp[i][j]==0)continue;
			for(int k=0;k<=m+20;k++){
				if(ok[1][k]){
					int dx=n-1-k-pos[i].second;
					int dy=n-1-(m+20-k)-pos[i].first;
					if(dx<0 || dy<0)continue;
					if(j%2==0){
						ans+=(mod_comb(dx+dy,dx,MOD)*dp[i][j]%MOD)*dp3[m+20-k][k]%MOD;
						ans%=MOD;
					}
					if(j%2==1){
						ans-=(mod_comb(dx+dy,dx,MOD)*dp[i][j]%MOD)*dp3[m+20-k][k]%MOD;;
						ans%=MOD;
						if(ans<0LL){
							ans+=MOD;
						}
					}
				}
			}
			
			for(int k=i+1;k<m+1;k++){
				int d1=pos[k].first-pos[i].first;
				int d2=pos[k].second-pos[i].second;
				if(d1>=0 && d2>=0){
					dp[k][j+1]+=dp[i][j]*mod_comb(d1+d2,d1,MOD)%MOD;
					dp[k][j+1]%=MOD;
				}
			}
		}
	}
	return ans;
}

ll calc(){
	memset(dist,-1,sizeof(dist));
	queue<P> que;
	for(int i=0;i<m;i++){
		if(y[i]<m+30 && x[i]<m+30)dist[y[i]][x[i]]--;
	}
	que.push(P(0,0));
	dist[0][0]=0;
	dp2[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=m+30 || ny<0 || ny>=m+30)continue;
			if(dist[ny][nx]==-1){
				dist[ny][nx]=dist[p.first][p.second]+1;
				dp2[ny][nx]+=dp2[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist[ny][nx]==dist[p.first][p.second]+1){
				dp2[ny][nx]+=dp2[p.first][p.second];
				dp2[ny][nx]%=MOD;
			}
		}
	}

	memset(dist2,-1,sizeof(dist2));
	for(int i=0;i<m;i++){
		if(y[i]>=n-(m-30) && x[i]>=n-(m-30))dist2[n-1-y[i]][n-1-x[i]]--;
	}
	que.push(P(0,0));
	dist2[0][0]=0;
	dp3[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=m+30 || ny<0 || ny>=m+30)continue;
			if(dist2[ny][nx]==-1){
				dist2[ny][nx]=dist2[p.first][p.second]+1;
				dp3[ny][nx]+=dp3[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist2[ny][nx]==dist2[p.first][p.second]+1){
				dp3[ny][nx]+=dp3[p.first][p.second];
				dp3[ny][nx]%=MOD;
			}
		}
	}
	int d_min=1LL<<30;
	for(int i=0;i<=m+20;i++){
		if(dist[m+20-i][i]>=0)d_min=min(d_min,dist[m+20-i][i]);
	}
	for(int i=0;i<=m+20;i++){
		if(d_min==dist[m+20-i][i]){
			ok[0][i]=true;
		}
	}
	d_min=1LL<<30;
	for(int i=0;i<=m+20;i++){
		if(dist2[m+20-i][i]>=0)d_min=min(d_min,dist2[m+20-i][i]);
	}
	for(int i=0;i<=m+20;i++){
		if(d_min==dist2[m+20-i][i]){
			ok[1][i]=true;
		}
	}
	ll ans=0;
	for(int i=0;i<=m+20;i++){
		if(ok[0][i]){
			ans+=calcdp(m+20-i,i)*dp2[m+20-i][i]%MOD;
			ans%=MOD;
		}
	}
	return ans;
}

ll bfs(){
	memset(dist,-1,sizeof(dist));
	queue<P> que;
	for(int i=0;i<m;i++){
		dist[y[i]][x[i]]--;
	}
	que.push(P(0,0));
	dist[0][0]=0;
	dp2[0][0]=1;
	while(que.size()){
		P p=que.front();
		que.pop();
		for(int i=0;i<4;i++){
			int nx=p.second+dx[i];
			int ny=p.first+dy[i];
			if(nx<0 || nx>=n || ny<0 || ny>=n)continue;
			if(dist[ny][nx]==-1){
				dist[ny][nx]=dist[p.first][p.second]+1;
				dp2[ny][nx]+=dp2[p.first][p.second];
				que.push(P(ny,nx));
			}else if(dist[ny][nx]==dist[p.first][p.second]+1){
				dp2[ny][nx]+=dp2[p.first][p.second];
				dp2[ny][nx]%=MOD;
			}
		}
	}
	return dp2[n-1][n-1];
}


int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&x[i],&y[i]);
		x[i]--;
		y[i]--;
	}
	if(n>=1000){
		fact[0]=1;
		for(int i=1;i<=n*2;i++){
			fact[i]=(ll)fact[i-1]*i%MOD;
		}
		printf("%lld\n",calc());
	}else{
		printf("%lld\n",bfs());
	}
	return 0;
} 

```