#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
#define MOD 1000000009
struct Matrix{
    long long n;

    Matrix(){
        memset(m,0,sizeof m);
    };
    long long m[80][80];
    Matrix operator * (const Matrix &b) const{
        Matrix c;
        for (long long i=0;i<n;i++)
        for (long long j=0;j<n;j++){
            c.m[i][j]=0;
            for (long long k=0;k<n;k++)
                c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%MOD)%MOD;
        }
        c.n=n;
        return c;
    }
};
Matrix ones;
Matrix Pow(const Matrix &a,long long n){
    Matrix t=ones,y=a;
    while (n){
        if (n & 1) t = (t * y) ;
        y = (y * y) ;
        n /= 2;
    }
    return t;
}
struct node{
    long long a,b;
}Pos[80];
bool cmp(node a,node b){
    return a.b<b.b;
}
Matrix A,B;
long long x[80];
void get_x(Matrix A){
    long long y[80];
    //printf("!!!");
    memset(y,0,sizeof y);
    for (long long i=0;i<A.n;i++){
        for (long long j=0;j<A.n;j++){
            y[i]=(y[i]+(x[j]*A.m[i][j])%MOD)%MOD;
        }
    }
    for (long long i=0;i<A.n;i++)
        x[i]=y[i];
}
long long sum;
long long w,n;
long long h;
long long k,p,q;
int main(){
    int i,j;
    int d=0;
    while (scanf("%lld%lld%lld",&w,&h,&n),w||h||n){
        memset(ones.m,0,sizeof ones.m);
        ones.n=w;
        for (i=0;i<w;i++)
            ones.m[i][i]=1;
        for (i=0;i<n;i++){
            scanf("%lld%lld",&Pos[i].a,&Pos[i].b);
            //Pos[i].a--;Pos[i].b--;
        }
        sort(Pos,Pos+n,cmp);

        memset(x,0,sizeof x);
        x[0]=1;
        memset(A.m,0,sizeof A.m);

        A.n=w;
        A.m[0][0]=1; A.m[0][1]=1;
        for (i=1;i<w;i++){
            A.m[i][i-1]=1;
            A.m[i][i]=1;
            A.m[i][i+1]=1;
        }
        //for (i=0;i<w;i++)
        //    x[i]=0;//蛻怜髄驥?        //k=0;
        //j=0;
        k = 0;
        j = 0;
        /*
        sort(Pos,Pos+n,cmp);
        //if ((w==0)&&(h==0)&&(n==0)) return 0;
        memset(x,0,sizeof x);
        x[0]=1;
        memset(A.m,0,sizeof A.m);

        A.n=w;
        A.m[0][0]=1;
        A.m[0][1]=1;
        for (i=1;i<w;i++){
            A.m[i][i]=1;
            A.m[i][i-1]=1;
            A.m[i][i+1]=1;
        }
        k=0;
        j=0;
        */

        // ****************************************
        /*
        int i,j;
    int d=0;
    while (scanf("%lld%lld%lld",&w,&h,&n),w||h||n){
        memset(ones.m,0,sizeof ones.m);
        for (i=0;i<w;i++)
            ones.m[i][i]=1;
        ones.n=w;
        for (i=0;i<n;i++)
            scanf("%lld%lld",&Pos[i].a,&Pos[i].b);
        sort(Pos,Pos+n,cmp);
        //if ((w==0)&&(h==0)&&(n==0)) return 0;
        memset(x,0,sizeof x);
        x[0]=1;
        memset(A.m,0,sizeof A.m);
        A.n=w;
        A.m[0][0]=1;
        A.m[0][1]=1;
        for (i=1;i<w;i++){
            A.m[i][i]=1;
            A.m[i][i-1]=1;
            A.m[i][i+1]=1;
        }
        k=0;
        j=0;
        */
        //****************************************
        //printf("!!!");
        while (j<n){
            p=Pos[j].b-1;
            if (k==p){
                x[Pos[j].a-1]=0;
            }
            else{
                get_x(Pow(A,p-k));
                k=p;
                x[Pos[j].a-1]=0;
            }
            //printf("%d",k);
            //for (int i=0;i<w;i++)
            //    printf("%5d",x[i]);
            //printf("\n");
            j++;

        }
        //printf("!!!");
        if (k<h-1){

//            B=Pow(A,h-1-k);printf("#!!!");
            get_x(Pow(A,h-1-k));
        }
        printf("Case %lld: %lld\n",++d,(x[w-1]%MOD+MOD)%MOD);
    }
}

Measured memory_bytes: 1628