#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using vl=vector<ll>;
using Mat=vector<vl>;
const ll MOD=1e9+9;



Mat cross(const Mat& a,const Mat& b){
    Mat res(a.size(),vl(a.size(),0));
    for(int i=0;i<a.size();i++){
        for(int k=0;k<a.size();k++){
            for(int j=0;j<a.size();j++){
                res[i][j]+=a[i][k]*b[k][j];
                res[i][j]%=MOD;
            }
        }
    }
    return res;
}

vl cross(const Mat& a,const vl& b){
    vl res(a.size(),0);
    for(int i=0;i<a.size();i++){
        for(int j=0;j<a.size();j++){
            res[i]+=a[i][j]*b[j];
            res[i]%=MOD;
        }
    }
    return res;
}

ll solve(int w,ll h,int n){
    vector<Mat> cals;
    cals.resize(64,Mat(w,vl(w)));
    for(int j=0;j<w;j++){
        for(int k=0;k<w;k++){
            cals[0][j][k]=(abs(k-j)<=1);
        }
    }
    for(int j=0;j+1<cals.size();j++){
        cals[j+1]=cross(cals[j],cals[j]);
    }

    set<pair<int,int>> ob;
    set<ll> hs;
    for(int i=0;i<n;i++){
        int x;
        ll y;
        cin>>x>>y;
        x--,y--;
        hs.insert(y);
        ob.insert({x,y});
    }
    hs.insert(0);
    hs.insert(h-1);
    vector<ll> hv(hs.begin(),hs.end());
    vector<vector<ll>> dp(hv.size(),vector<ll>(w,0));
    dp[0][0]=1;
    for(int i=1;i<hv.size();i++){
        ll dist=hv[i]-hv[i-1];
        vector<ll> next=dp[i-1];
        for(int j=0;j<64 && dist;j++){
            if(dist%2) next=cross(cals[j],next);
            dist/=2;
        }
        for(int j=0;j<w;j++){
            if(!ob.count({j,hv[i]})) dp[i][j]=next[j];
        }
    }
    return dp[hv.size()-1][w-1];
}

int main(){
    int w,n;
    ll h;
    int i=0;
    while(cin>>w>>h>>n,w){
        i++;
        cout<<"Case "<<i<<": "<<solve(w,h,n)<<endl;
    }
    return 0;
}