#include<iostream>
#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
#include <sys/time.h>
#include <sys/resource.h>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)

double e_time(void){
  static struct timeval now;
  gettimeofday(&now, NULL);
  return (double)(now.tv_sec  + now.tv_usec/1000000.0);
} 

const int N = 75;
typedef long long ll;
const ll mod = 1000000000+9;
const int dx[]={-1,0,1};
ll mat[N][N],buf[N][N],ori[N][N];
void matmul(int n,ll c[N][N],ll a[N][N],ll b[N][N]){
  rep(i,n)rep(j,n)buf[i][j]=0;
  rep(i,n){
    rep(j,n){
      buf[i][j]=0;
      rep(k,n){
	ll tmp = (a[i][k]*b[k][j])%mod;
	buf[i][j] += tmp;
	buf[i][j] %= mod;
      }
    }
  }
  rep(i,n)rep(j,n)c[i][j]=buf[i][j];
}
void matpow(int n,ll p,ll mat[N][N],ll ori[N][N]){
  if (p == 1){
    rep(i,n)rep(j,n)mat[i][j]=ori[i][j];
    return;
  }
  matpow(n,p/2,mat,ori);
  matmul(n,mat,mat,mat);
  if (p%2 == 1)matmul(n,mat,mat,ori);
  return;
}

ll A[64][N][N];
void precomp(int c){
  rep(i,c){
    rep(j,c)ori[i][j] = 0;
  }
  rep(i,c){
    if (i-1>=0)ori[i][i-1] = 1;
    ori[i][i] = 1;
    if (i+1< c)ori[i][i+1] = 1;
  }
  rep(i,c)rep(j,c)A[0][i][j] = ori[i][j];
  ll p = 2;
  REP(i,1,64){
    matmul(c,A[i],A[i-1],A[i-1]);
    p <<= 2;
  }
}

void matvec(int c,ll p,vector<ll> & vec){
  vector<ll> next(c);
  rep(i,63){
    if ((1LL<<i)&p){
      rep(ii,c){
	next[ii] = 0;
	rep(jj,c){
	  next[ii] += (A[i][ii][jj]*vec[jj]);
	  next[ii] %= mod;
	}
      }
      vec = next;
    }
  }
}

ll solve(ll r,ll c,vector<pair<ll,int> > in){
  vector<ll> y;
  rep(i,(int)in.size())y.push_back(in[i].first);
  y.push_back(r-1);
  sort(y.begin(),y.end());
  y.erase(unique(y.begin(),y.end()),y.end());

  vector<ll> cur(c);
  rep(i,c)cur[i] = 0;cur[0] = 1;
  
  rep(i,c)rep(j,c)ori[i][j] = 0;
  rep(i,c){
    if (i)ori[i][i-1] =1;
    ori[i][i] = 1;
    if (i+1<c)ori[i][i+1]=1;
  }

  ll lasty = 0;
  rep(k,y.size()){
    ll p = y[k]-lasty;
    lasty = y[k];
    if (p != 0){
      matvec(c,p,cur);
    }
    rep(i,in.size()){
      if (y[k] == in[i].first)cur[in[i].second] = 0;
    }
  }
  return cur[c-1];
}

main(){
  int c,n;
  ll r;
  int tc = 1;
  while(cin>>c>>r>>n && r){
    precomp(c);
    vector<pair<ll,int> > in;
    rep(i,n){
      ll y;
      int x;
      cin>>x>>y;
      y--;x--;
      in.push_back(make_pair(y,x));
    }
    ll ans = solve(r,c,in);
    cout <<"Case " << tc++ << ": " << ans << endl;
  }
  return 0;
}