#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;
}


### Prompt

Create a solution in CPP for 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>
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;
}


```