#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define FOREQ(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef vector<ll> Array;
typedef vector<Array> Matrix;
const ll MOD = 1e+9 + 9;
ll w, h, n;
ll m;
ll field[100][100];
ll Y[100];
ll ys[100];
ll xs[100];
Matrix p2[100];

void PrintMatrix(const Matrix &mat) {
  REP(y, mat.size()) {
    REP(x, mat[y].size()) {
      printf("%lld ", mat[y][x]);
    }
    puts("");
  }
  puts("");
}

Matrix Mul(const Matrix &lhs, const Matrix &rhs) {
  const ll h = lhs.size();
  const ll in = lhs[0].size();
  const ll w = rhs[0].size();
  assert(lhs[0].size() == rhs.size());
  Matrix ret(h, Array(w, 0));
  REP(y, h) REP(i, in) REP(x, w) {
    ret[y][x] = (ret[y][x] + lhs[y][i] * rhs[i][x]) % MOD;
  }
  return ret;
}

void Make(ll n) {
  p2[0] = Matrix(n, Array(n, 0));
  p2[1] = Matrix(n, Array(n, 0));
  REP(x, n) {
    p2[0][x][x] = 1;
    FOREQ(dx, -1, 1) {
      if (0 <= x + dx && x + dx < n) { p2[1][x][x + dx] = 1; }
    }
  }
  FOREQ(i, 1, 64) { p2[i + 1] = Mul(p2[i], p2[i]); }
}

void PowMod(ll power, Matrix &vect) {
  ll index = 0;
  while (power > 0) {
    if (power & 1) { vect = Mul(p2[index + 1], vect); }
    index++;
    power >>= 1;
  }
}

int main() {
  int test_case = 0;
  while (scanf("%lld %lld %lld", &w, &h, &n), w|h|n) {
    test_case++;
    Make(w);
    MEMSET(field, 0);
    {
      set<ll> open;
      open.insert(0);
      open.insert(h - 1);
      REP(i, n) {
        scanf("%lld %lld", &xs[i], &ys[i]);
        xs[i]--; ys[i]--;
        while (xs[i] < 0 || xs[i] >= w || ys[i] < 0 || ys[i] >= h) {
          continue;
        }
        open.insert(ys[i] - 1);
        open.insert(ys[i]);
        open.insert(ys[i] + 1);
      }
      map<ll, ll> mapto;
      m = 0;
      FORIT(it, open) {
        if (*it < 0 || *it >= h) { continue; }
        Y[m] = *it;
        mapto[*it] = m++;
      }
      REP(i, n) {
        field[mapto[ys[i]]][xs[i]] = 1;
      }
    }
    Matrix prev(w, Array(1, 0));
    prev[0][0] = 1;
    REP(y, m - 1) {
      Matrix next(w, Array(1, 0));
      if (Y[y + 1] - Y[y] == 1) {
        REP(x, w) {
          FOREQ(dx, -1, 1) {
            if (x + dx < 0 || x + dx >= w) { continue; }
            if (field[y + 1][x + dx] == 1) { continue; }
            next[x + dx][0] += prev[x][0];
          }
        }
      } else {
        next = prev;
        PowMod(Y[y + 1] - Y[y], next);
      }
      prev = next;
    }
    printf("Case %d: %lld\n", test_case, prev[w - 1][0]);
  }
}