#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;


ll M=1e9+9;
ll dp[100][100][100];


int main(){
  ll w,h,n;
  ll T=1;

  while(cin>>w>>h>>n,w){

    vector<P> v;
    for(ll x,y,i=0;i<n;i++){

      cin>>x>>y;
      v.push_back(P(y-1,x-1));
      
    }
    
    sort(v.begin(),v.end());
    ll bt=0;

    memset(dp,0,sizeof(dp));
    
    for(ll i=0;i<w;i++)
      for(ll j=max(0LL,i-1);j<=min(w-1,i+1);j++)
	dp[0][i][j]=1;
  
    h--;

    while((1LL<<bt)<=h){
 
      for(ll i=0;i<w;i++)
	for(ll j=0;j<w;j++)
	  for(ll k=0;k<w;k++)
	    dp[bt+1][j][k]=(dp[bt][j][i]*dp[bt][i][k]+dp[bt+1][j][k])%M;
      
      bt++;
    }

    ll pr=0;

    v.push_back(P(h,-1));

    ll ans[100]={};

    ans[0]=1;
    
    for(ll p=0;p<=n;p++){
      bt=0;
      ll nh=v[p].first-pr;
      pr=v[p].first;
      while((1LL<<bt)<=nh){
	if((1LL<<bt)&nh){
	  ll tmp[100]={};
	  
	  for(ll i=0;i<w;i++)
	    for(ll j=0;j<w;j++)
	      tmp[j]=(tmp[j]+ans[i]*dp[bt][i][j])%M;
	  
	  for(ll i=0;i<w;i++)ans[i]=tmp[i];
	  
	}
	bt++;
      }

      ll yy=v[p].first;

      while(p<=n&&v[p].first==yy){
	if(v[p].second!=-1)ans[v[p].second]=0;
	p++;
      }
      
      p--;
      
    }
    cout<<"Case "<<T++<<": ";
    cout<<ans[w-1]<<endl;

  }



  return 0;
}