#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

const int mod = 1000000009;

struct Mat{
  int v[80][80];
  int h,w;

  Mat():h(0),w(0){}
  Mat(int h, int w):h(h),w(w){}
};

void showMat(const Mat &a){
  cout << "height : " << a.h << ", width : " << a.w << endl;
  for(int i = 0; i < a.h; ++i){
    for(int j = 0; j < a.w; ++j){
      cout << a.v[i][j] << ' ';
    }
    cout << endl;
  }
  cout << " ----- " << endl;
}

// #define NAIVE
#ifndef NAIVE
Mat operator * (const Mat &a, const Mat &b){
  // only this problem
  Mat c(a.h,b.w);
  for(int i = 0; i < a.h; ++i){
    for(int j = 0; j <= i && j <= a.h - i - 1; ++j){
      c.v[i][j] = 0;
      for(int k = 0; k < a.w; ++k){
        c.v[i][j] += (long long)a.v[i][k] * b.v[k][j] % mod;
        c.v[i][j] %= mod;
      }
      c.v[j][i]             = c.v[i][j];
      c.v[c.h-i-1][c.w-j-1] = c.v[i][j];
      c.v[c.w-j-1][c.w-i-1] = c.v[i][j];
    }
  }
  return c;
}
#else
Mat operator * (const Mat &a, const Mat &b){
  // only this problem
  Mat c(a.h,b.w);
  for(int i = 0; i < a.h; ++i){
    for(int j = 0; j < b.w; ++j){
      c.v[i][j] = 0;
      for(int k = 0; k < a.w; ++k){
        c.v[i][j] += (long long)a.v[i][k] * b.v[k][j] % mod;
        c.v[i][j] %= mod;
      }
      // c.v[j][i]             = c.v[i][j];
      // c.v[c.h-i-1][c.w-j-1] = c.v[i][j];
      // c.v[c.w-j-1][c.w-i-1] = c.v[i][j];
    }
  }
  return c;
}
#endif

vector<Mat> A2;

Mat power(const Mat &a, long long e)
{
  Mat x = a;
  Mat ret(a.h,a.w);
  
  for(int i = 0; i < ret.h; ++i){
    for(int j = 0; j < ret.w; ++j){
      ret.v[i][j] = i == j ? 1 : 0;
    }
  }
  A2[0] = ret;

  int ref = 1;
  while(e){
    // cout << "e : " << e << ", ref : " << ref << endl;
    if(e&1)ret=ret*A2[ref];
    ++ref;
    e>>=1;
  };
  
  return ret;
}

int solve(int w, long long h, int n, const vector<pair<long long, int> > &st)
{
  long long pre = 0;
  Mat b1(w,1), b2(w,1);
  Mat A(w,w);

  for(int i = 0; i < w; ++i){
    b1.v[i][0] = 0;
    b2.v[i][0] = 0;
  }
  b1.v[0][0] = 1;
  for(int i = 0; i < w; ++i){
    for(int j = 0; j < w; ++j){
      if( abs(i-j) <= 1 ) A.v[i][j] = 1;
      else A.v[i][j] = 0;
    }
  }

  A2.clear();
  A2.push_back(A);
  A2.push_back(A);
  for(int i = 2; i < 70; ++i){
    A2.push_back( A2[i-1] * A2[i-1] );
  }
  
  for(int i = 0; i < n; ++i){
    Mat Ae = power(A, st[i].first - pre);
    for(int j = 0; j < w; ++j){
      for(int k = 0; k < w; ++k){
        b2.v[j][0] += (long long)Ae.v[j][k] * b1.v[k][0] % mod;
        b2.v[j][0] %= mod;
      }
    }

    for(int j = 0; j < w; ++j){
      b1.v[j][0] = j!=st[i].second?b2.v[j][0]:0;
      b2.v[j][0] = 0;
    }

    pre = st[i].first;
  }

  return b1.v[w-1][0];
}

int main()
{
  int W,N;
  long long H;
  int tc = 1;

  while( cin >> W >> H >> N ){
    if( W == 0 && H == 0 && N == 0 ) break;
    
    vector<pair<long long,int> > stones;
    for(int i = 0; i < N; ++i){
      int x;
      long long y;
      cin >> x >> y;
      stones.push_back(make_pair(y-1,x-1));
    }
    stones.push_back(make_pair(H-1,W));
    sort(stones.begin(),stones.end());
    
    int res = solve(W,H,N+1,stones);

    cout << "Case " << tc << ": " << res << endl;
    ++tc;
  }
  return 0;
}

Measured memory_bytes: 2952