#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long lli;
typedef lli elm;
typedef vector<vector<elm> > mat;

const lli mod = 1000000009LL;

mat getE(int n) {
  mat e(n, vector<elm>(n, 0));
  for(int i = 0; i < n; ++i) {
    e[i][i] = 1;
  }
  return e;
}

mat multiply(const mat &a, const mat &b) {
  if(a.size() == 0 || b.size() == 0 ||
     a[0].size() != b.size()) return mat();
  int s = a.size();
  int t = b.size();
  int u = b[0].size();
  mat c(s, vector<elm>(u, 0));
  for(int i = 0; i < s; ++i) {
    for(int j = 0; j < u; ++j) {
      for(int k = 0; k < t; ++k) {
        c[i][j] += (a[i][k] * b[k][j]) % mod;
        c[i][j] %= mod;
      }
    }
  }
  return c;
}

mat pow(const mat &a, const lli &n) {
  if(n == 0) return getE(a.size());
  mat b = pow(multiply(a, a), n/2);
  if(n & 1) return multiply(b, a);
  else return b;
}

lli W, H, N;
vector<pair<lli,lli> > pos;

int main() {
  while(cin >> W >> H >> N && (W|H|N)) {
    pos.clear();
    for(int i = 0; i < N; ++i) {
      lli x, y;
      cin >> x >> y;
      pos.push_back(make_pair(y-1,x-1));
    }
    pos.push_back(make_pair(H-1,0));
    ++N;
    sort(pos.begin(), pos.end());
    mat A = getE(W);
    for(int i = 0; i < W; ++i) {
      for(int j = 0; j < W; ++j) {
        A[i][j] = (abs(i-j) <= 1);
      }
    }
    mat x = vector<vector<lli> >(1, vector<lli>(W, 0LL));
    x[0][0] = 1LL;
    for(lli i = 0, y = 0; i < N; ) {
      lli dy = pos[i].first - y;
      y = pos[i].first;
      x = multiply(x, pow(A,dy));
      while(i < N && pos[i].first == y) {
        x[0][pos[i++].second] = 0;
      }
    }
    static int tc = 0;
    cout << "Case " << ++tc << ": " << x[0][W-1] << endl;
  }
  return 0;
}