#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define rep(i, n) for(int i = 0; i< (int)(n); i++)
#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define pb(e) push_back(e)
#define foreach(c, i) for(iter(c) i = (c).begin(); i != c.end(); ++i)

typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000 * 1000 * 1000 + 9;
const double EPS = 1e-10;

const int sz = 60;
const int smalln = 510;
const int maxn = 2000010;
int X[sz], Y[sz];
ll p[maxn], p_inv[maxn];
bool ng[smalln][smalln];
int dist[smalln][smalln];
ll memo[smalln][smalln];
ll dp[sz][sz][2];

ll modpow(ll p, ll n, ll mod){
  ll res = 1;
  while(n > 0){
    if(n & 1){
      res = (res * p) % mod;
    }
    p = (p * p) % mod;
    n >>= 1;
  }
  return res;
}

void init(){
  p[0] = 1;
  p_inv[0] = 1;
  rep(i, maxn - 1){
    p[i+1] = p[i] * (i + 1) % mod;
    p_inv[i+1] = modpow(p[i+1], mod - 2, mod);
  }
}

ll comb(int n, int r){
  if(n < r) return 0;
  ll res = p[n] * p_inv[r] % mod;
  return res * p_inv[n-r] % mod;
}

ll bfs(int N, int M){
  int dx[] = {0, 1, 0, -1};
  int dy[] = {1, 0, -1, 0};
  memset(ng, false, sizeof(ng));
  memset(memo, 0, sizeof(memo));
  memset(dist, -1, sizeof(dist));

  rep(i, M) if(X[i] < smalln && Y[i] < smalln) ng[X[i]][Y[i]] = true;
  
  memo[1][1] = 1;
  queue<P> que;
  que.push(P(1, 1));

  while(!que.empty()){
    int x = que.front().first;
    int y = que.front().second;
    que.pop();
    rep(i, 4){
      int x2 = x + dx[i];
      int y2 = y + dy[i];
      if(1 <= x2 && x2 <= N && 1 <= y2 && y2 <= N && !ng[x2][y2] && 
	 (dist[x2][y2] < 0 || dist[x2][y2] >= dist[x][y] + 1)){
	if(dist[x2][y2] != dist[x][y] + 1){
	  dist[x2][y2] = dist[x][y] + 1;
	  que.push(P(x2, y2));
	}
	memo[x2][y2] += memo[x][y];
	memo[x2][y2] %= mod;
      }
    }
  }
  return memo[N][N];
}

ll calc(int M, int x1, int x2, int y1, int y2){
  ll res = 0;
  
  memset(dp, 0, sizeof(dp));
  dp[0][0][0] = 1;

  rep(i, M) rep(j, i + 1)rep(k, 2){
    dp[i+1][j][k] += dp[i][j][k];
    dp[i+1][j][k] %= mod;
    
    int prex = j == 0 ? x1 : X[j-1];
    int prey = j == 0 ? y1 : Y[j-1];
    int dx = X[i] - prex;
    int dy = Y[i] - prey;
    if(dx >= 0 && dy >= 0){
      dp[i+1][i+1][1 - k] += dp[i][j][k] * comb(dx + dy, dx);
      dp[i+1][i+1][1 - k] %= mod;
    }
  }
  
  rep(i, M + 1){
    int lastx = i == 0 ? x1 : X[i-1];
    int lasty = i == 0 ? y1 : Y[i-1];
    int dx = x2 - lastx;
    int dy = y2 - lasty;

    if(dx >= 0 && dy >= 0){
      res += (dp[M][i][0] - dp[M][i][1]) * comb(dx + dy, dx) % mod;
    }
  }
  return (res % mod + mod) % mod;
}

int solve(int N, int M){
  ll res = 0;
  ll cnt1[2 * sz], cnt2[2 * sz];
  int best = (int)1e9, len = 2 * M + 1;
  int tempX[sz], tempY[sz];
  
  bfs(len, M);

  rep(i, len) best = min(best, dist[i+1][len-i]);
  rep(i, len) cnt1[i+1] = best == dist[i+1][len-i] ? memo[i+1][len-i] : 0;
  
  rep(i, M) tempX[i] = N + 1 - X[i], tempY[i] = N + 1 - Y[i];
  swap(X, tempX);
  swap(Y, tempY);
  best = (int)1e9;
  bfs(len, M);
  rep(i, len) best = min(best, dist[i+1][len-i]);
  rep(i, len) cnt2[i+1] = best == dist[i+1][len-i] ? memo[i+1][len-i] : 0;
  
  swap(X, tempX);
  swap(Y, tempY);  
  
  for(int x1 = 1; x1 <= len; x1++){
    for(int x2 = N; x2 > N - len; x2--){
      int y1 = len + 1 - x1;
      int y2 = 2 * N - len - x2 + 1;
      ll temp = calc(M, x1, x2, y1, y2) * cnt1[x1] % mod;
      temp = temp * cnt2[N-x2+1] % mod;
      //cout << x1 << " " << y1 << " " << x2 << " " << y2 << "  "<< cnt1[x1] << " " << cnt2[N-x2+1]  << endl;
      res += temp;
    }
  }
  return res % mod;
}

int main(){
  int N, M;
  cin >> N >> M;
  init();
  rep(i, M) cin >> X[i] >> Y[i];
  
  rep(i, M)rep(j, M - 1) if(X[j] > X[j+1] || (X[j] == X[j+1] && Y[j] > Y[j+1])){
    swap(X[j], X[j+1]);
    swap(Y[j], Y[j+1]);
  }
  
  if(N < 500){
    cout << bfs(N, M) << endl;
  }else{
    cout << solve(N, M) << endl;
  }
  return 0;
}

Measured memory_bytes: 35840