require 'set'

MOD = 10 ** 9 + 9

$fact = [1]
(1..2*10**6).each do |i|
  $fact << $fact[-1] * i % MOD
end

def comb(n, k)
  $fact[n] * inv($fact[k]) * inv($fact[n - k]) % MOD
end

def inv(k)
  exp(k, MOD - 2, MOD)
end

def exp(n, k, mod = nil)
    x = 1
    r = n
    while k > 0
        x *= r if k & 1 == 1
        r *= r
        if mod
            x %= mod
            r %= mod
        end
        k >>= 1
    end
    x
end

n, m = gets.split.map(&:to_i)
points = (1..m).map { gets.split.map(&:to_i) }.map {|x, y| [x - 1, y - 1] }.sort_by {|x, y| x + y }

def bfs(n, m, points, xs, ys)
  s = [xs, ys]
  reached = Set[s]
  reached += points
  queue = [s]
  count = Hash.new(0)
  count[s] = 1
  dist = { s => 0 }
  until queue.empty?
    x, y = queue.shift
    k = count[[x, y]]
    d = dist[[x, y]]
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dx, dy|
      u, v = x + dx, y + dy
      count[[u, v]] += k if dist[[u, v]] == nil or dist[[u, v]] == d + 1
      next if reached.include?([u, v]) or
        u < 0 or u >= n or
        v < 0 or v >= n or
        (xs - u).abs + (ys - v).abs > m
      reached << [u, v]
      dist[[u, v]] = d + 1
      queue << [u, v]
    end
  end
  return [dist, count]
end

if n <= 150
  _, count = bfs(n, 2 * n, points, 0, 0)
  puts (count[[n - 1, n - 1]] || 0) % MOD
  exit
end

dist1, count1 = bfs(n, m, points, 0, 0)
dist2, count2 = bfs(n, m, points, n - 1, n - 1)

d = (0..m).map {|i| dist1[[i, m - i]] || -Float::INFINITY }.min
starts = (0..m).map {|i| [i, m - i] }.select {|v| dist1[v] == d }
d = (0..m).map {|i| dist2[[n - 1 - i, n - 1 - m + i]] || -Float::INFINITY }.min
ends = (0..m).map {|i| [n - 1 - i, n - 1 - m + i] }.select {|v| dist2[v] == d }

total = 0
starts.each do |xs, ys|
  xe, ye = n - 1, n - 1
  ends.each do |xe, ye|
    valid_points = points.select {|x, y| (xs..xe) === x && (ys..ye) === y } + [[xe, ye]]
    a = []
    (0..valid_points.size-1).each do |i|
      x1, y1 = valid_points[i]
      c = comb(x1 - xs + y1 - ys, x1 - xs)
      (0..i-1).each do |j|
        x2, y2 = valid_points[j]
        next if x2 > x1 or y2 > y1
        c = (c - a[j] * comb(x1 - x2 + y1 - y2, x1 - x2)) % MOD
      end
      a << c
    end
    total += count1[[xs, ys]] * a[-1] * count2[[xe, ye]] % MOD
  end
end
p total % MOD

