#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back

const ll MOD = (1e9)+9;

template<class T>
class matrix{
public:
    vector<vector<T>> elm;
    int height,width;
    
    matrix():height(0),width(0){};
    matrix(int h,int w):height(h),width(w){
        elm.resize(h,vector<T>(w,0));    //0-padding
    }
    
//    matrix<T> operator + (const matrix &m)const{
//        matrix<T> ret(this->height,this->width);
//        ret.elm = this->elm;
//        rep(i,height) rep(j,width) ret.elm[i][j] += m.elm[i][j];
//        return ret;
//    }
//    matrix<T> operator - (const matrix &m)const{
//        matrix<T> ret(this->height,this->width);
//        ret.elm = this->elm;
//        rep(i,height) rep(j,width) ret.elm[i][j] -= m.elm[i][j];
//        return ret;
//    }
//    matrix<T> operator / (const T &number)const{
//        matrix<T> ret(this->height,this->width);
//        ret.elm = this->elm;
//        rep(i,height) rep(j,width) ret.elm[i][j] /= number;
//        return ret;
//    }
//    matrix<T> operator * (const double &number)const{
//        matrix<T> ret(this->height,this->width);
//        ret.elm = this->elm;
//        rep(i,height) rep(j,width) ret.elm[i][j] *= number;
//        return ret;
//    }
    matrix<T> operator * (const matrix &m)const{
        assert(width==m.height);
        matrix<T> ret(height,m.width);
        rep(i,height){
            rep(j,m.width){
                rep(k,width){
                    (ret.elm[i][j] += elm[i][k]*m.elm[k][j])%=MOD;
                }
            }
        }
        return ret;
    }
    
//    void output(){
//        rep(i,height){
//            rep(j,width){
//                if(j)cout<<" ";
//                cout<<elm[i][j];
//            }
//            cout<<endl;
//        }
//        cout<<endl;
//    }
    
//    matrix<T> tern(){
//        matrix<T> ret(width,height);
//        rep(i,height) rep(j,width) ret.elm[j][i] = elm[i][j];
//        return ret;
//    }
    
//    matrix<T> inv(){
//        assert(height==width);
//        int N = height;
//
//        matrix<T> mat(height,width*2);
//        rep(i,N)rep(j,N)mat.elm[i][j] = this->elm[i][j];
//        rep(i,N)mat.elm[i][width+i] = 1;
//
//        double div;
//        rep(i,N){
//            int pivot = i;
//            rep(j,N){
//                if( abs(mat.elm[pivot][i]) < abs(mat.elm[j][i]) )pivot = j;
//            }
//            swap( mat.elm[i],mat.elm[pivot] );
//
//            div = mat.elm[i][i];
//            rep(j,N*2)mat.elm[i][j] /=div;
//            rep(ii,N){
//                if(i==ii)continue;
//                double k = mat.elm[ii][i];
//                rep(j,N*2){
//                    mat.elm[ii][j]-=k*mat.elm[i][j];
//                }
//            }
//        }
//
//        matrix<T> ret(N,N);
//
//        rep(i,N)copy(mat.elm[i].begin()+N,mat.elm[i].end(),ret.elm[i].begin());
//        rep(i,N)if(mat.elm[i][i]!=1)return matrix<T>(0,0);
//        return ret;
//    }
};

matrix<int> power(matrix<int> mt, int t){
    if(t==0){
        int w = mt.width;
        matrix<int> tmp(w,w);
        rep(i,w)tmp.elm[i][i] = 1;
        return tmp;
    }else{
        matrix<int> ret = power(mt,t/2);
        if(t%2==0)return ret*ret;
        else return ret*ret*mt;
    }
}

signed main(){
    int w,h,n;
    int case_num = 0;
    while(cin>>w>>h>>n&&(w||h||n)){
        case_num++;
        matrix<int> mt(1,w);
        mt.elm[0][0] = 1;
        
        matrix<int> emp(w,w);
        rep(i,w){
            rep(j,w){
                if( abs(i-j)<=1 )emp.elm[i][j] = 1;
                else emp.elm[i][j] = 0;
            }
        }
        
        set<pii> obstructions;
        set<int> y;
        rep(i,n){
            int a,b;
            cin>>a>>b;
            a--,b--;
            if(b==0)continue;
            y.insert(b);
            obstructions.insert(pii(b,a));
        }
        
        
        
        int cur = 0;
        for(auto elm:y){
            int times = elm-cur-1;
            assert(times>=0);
            mt = mt*(power(emp,times));
            
            vector<int> tmp(w);
            rep(j,w){
                if(obstructions.count(pii(elm,j))==0){
                    for(int k=max<ll>(0,j-1);k<=min<ll>(w-1,j+1);k++){
                        (tmp[j] += mt.elm[0][k])%=MOD;
                    }
                }
            }
            mt.elm[0] = tmp;
            cur = elm;
        }
        mt = mt*(power(emp,h-1-cur));
        cout<<"Case "<<case_num<<": "<<mt.elm[0][w-1]<<endl;
    }
}





Measured memory_bytes: 5864