#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000009;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

typedef vector<ll> Array;
typedef vector<Array> Matrix;

// 行列の掛け算 O(N * M * S)
Matrix mul(const Matrix& a, const Matrix& b){
  int N = a.size(), M = b[0].size(), S = a[0].size();
  assert(S == b.size());
  Matrix c(N, Array(M));
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      for(int k = 0; k < S; k++){
        c[i][j] += a[i][k] * b[k][j];
        c[i][j] %= MOD;
      }
    }
  }
  return c;
}
// 正方行列の累乗 O(N^3 * logn)
Matrix pow(Matrix a, long long b){
  int N = a.size();
  Matrix c(N, Array(N));
  REP(i, N) c[i][i] = 1;
  while(b > 0){
    if(b & 1) c = mul(c, a);
    a = mul(a, a);
    b >>= 1;
  }
  return c;
}
void print(Matrix m){
  REP(i, m.size()){
    REP(j, m[i].size()) cout << m[i][j] << " ";
    cout << endl;
  }
}

int solve(ll W, ll H, vector<ll> ys, map<ll, vector<ll> > xmp){
  Matrix T(W, Array(W));
  REP(i, W) REP(j, W) if(abs(i - j) <= 1) T[i][j] = 1;
  Matrix A(W, Array(W));
  REP(i, W) REP(j, W) A[i][j] = (i == j) ? 1 : 0;
  for(int i = 1; i < ys.size(); i++){
    ll b = (ys[i] - ys[i - 1]);
    A = mul(pow(T, b), A);
    // Erase
    Matrix M(W, Array(W));
    REP(j, W) M[j][j] = 1;
    REP(j, xmp[ys[i]].size()){
      ll x = xmp[ys[i]][j];
      M[x][x] = 0;
    }
    A = mul(M, A);
    //print(A);
    //cout << endl;
  }
  return A[W - 1][0];
}
int solve2(ll W, ll H, int N, vector<ll> x, vector<ll> y){
  if(H > 10000) assert(false);
  if(H > 10000) return -1;
  ll dp[10000][75] = {};
  //memset(dp, 0, sizeof(dp));
  bool bad[10000][75] = {};
  //memset(bad, 0, sizeof(bad));
  REP(i, N) bad[y[i]][x[i]] = true;
  dp[0][0] = 1;
  for(int y = 0; y + 1 < H; y++){
    for(int x = 0; x < W; x++){
      for(int dx = -1; dx <= 1; dx++){
        if(x + dx >= 0 && x + dx < W && !bad[y + 1][x + dx]){
          dp[y + 1][x + dx] += dp[y][x];
          dp[y + 1][x + dx] %= MOD;
        }
      }
    }
    //cout << y + 1 << ": "; REP(x, W) cout << dp[y + 1][x] << " "; cout << endl;
  }
  return dp[H - 1][W - 1];
}
int main(){
  ll W, H;
  int N;
  int C = 1;
  while(cin >> W >> H >> N && W){
    vector<ll> ys;
    map< ll, vector<ll> > xmp;
    ys.push_back(0); ys.push_back(H - 1);
    vector<ll> x(N), y(N);
    REP(i, N){
      cin >> x[i] >> y[i];
      x[i]--; y[i]--;
      ys.push_back(y[i]);
      xmp[y[i]].push_back(x[i]);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    printf("Case %d: ", C++);
    //assert(solve(W, H, ys, xmp) == solve2(W, H, N, x, y));
    //cout << solve2(W, H, N, x, y) << endl;
    cout << solve(W, H, ys, xmp) << endl;
  }
  return 0;
}

Measured memory_bytes: 1496