// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

#define MOD 1000000009

long long w,h,n;

struct Matrix{

    long long n,m[80][80];

    Matrix  operator * (const Matrix &b)const{

        Matrix c;

        memset(c.m,0,sizeof c.m);

        c.n=n;

        for (int i=0;i<n;i++)

        for (int j=0;j<n;j++)

        for (int k=0;k<n;k++){

            c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%MOD)%MOD;

        }

        return c;

    }

};

Matrix ones;

Matrix Pow(const Matrix &a,unsigned long long n){

    Matrix t=ones,y=a;

    while (n){

        if (n & 1) t = (t * y) ;

        y = (y * y) ;

        n /= 2;

    }

    return t;

}

Matrix A;

long long x[80];

long long k,p,q;

struct node{

    long long a,b;

};

node Pos[80];

int cmp(node a,node b){

    return a.b<b.b;

}

void get_x(Matrix a){

    long long y[80];

    memset(y,0,sizeof y);

    for (int i=0;i<a.n;i++){

        for (int j=0;j<a.n;j++){

            y[i]=(y[i]+(x[j]*a.m[i][j])%MOD)%MOD;

        }

    }

    for (int i=0;i<a.n;i++)

        x[i]=y[i];

}

int main(){

    int i,j;

    int d=0;

    while (scanf("%lld%lld%lld",&w,&h,&n)!=EOF){

        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;

        while (j<n){

            p=Pos[j].b-1;

            if (p==k){

                x[Pos[j].a-1]=0;

            }

            else{

                get_x(Pow(A,p-k));

                k=p;

                x[Pos[j].a-1]=0;

            }

            j++;

        }

        if (k<h-1){

            get_x(Pow(A,h-1-k));

        }

        printf("Case %d: %lld\n",++d,x[w-1]);

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.2808508481518743x):
#include <cstdio>

#include <vector>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <map>

using namespace std;



typedef long long LL;

const int maxn = 75, MOD = 1000000009;



int n, N;

LL m;

map<LL, vector<LL> > s;



class Matrix {

public:

	LL val[maxn][maxn];

	Matrix() {

		memset(val, 0, sizeof(val));

	}



	Matrix operator*(const Matrix& c) const {

		Matrix res;

		for (int i = 0; i < n; ++i)

			for (int j = 0; j < n; ++j)

				for (int k = 0; k < n; ++k) {

					res.val[i][j] += val[i][k] * c.val[k][j];

					res.val[i][j] = (res.val[i][j] + MOD) % MOD; //髦イ豁「遏ゥ髦オ蜈?エ?序荳コ雍滓焚?瑚凶荳埼怙隕?シ悟悉謗?+MOD"

				}

		return res;

	}



	Matrix& operator*=(const Matrix& c) {

		*this = *this * c;

		return *this;

	}



	Matrix Pow(LL k) { //霑泌屓one^k

		Matrix res = Zero();

		Matrix step = One();

		while (k) {

			if (k & 1)

				res *= step;

			k >>= 1;

			step *= step;

		}

		return res;

	}



	Matrix Zero() const {

		Matrix res;

		for (int i = 0; i < maxn; ++i)

			res.val[i][i] = 1;

		return res;

	}



	Matrix One() const {

		Matrix res;

		res.val[0][0] = res.val[0][1] = 1;

		res.val[n-1][n-1] = res.val[n-1][n-2] = 1;

		for (int i = 1; i < n - 1; ++i) {

			res.val[i][i-1] = res.val[i][i] = res.val[i][i + 1] = 1;

		}

		return res;

	}

};



int main() {

	int kcase = 0;

	while (scanf("%d%lld%d", &n, &m, &N) && n) {

		s.clear();

		for (int i = 0; i < N; ++i) {

			LL x, y;

			scanf("%lld%lld", &x, &y);

			s[--y].push_back(--x);

		}

		if (n == 1) {

			if (N) {

				printf("Case %d: 0\n", ++kcase);

			} else {

				printf("Case %d: 1\n", ++kcase);

			}

			continue;

		}

		Matrix res;

		res.val[0][0] = 1;

		LL now = 0;

		for (map<LL, vector<LL> >::iterator it = s.begin(); it != s.end(); ++it) {

			if (it -> first == 0) continue;

			res *= res.Pow((it -> first) - now);

			now = it -> first;

			for (int i = 0; i < (it -> second).size(); ++i) {

				res.val[0][(it -> second)[i]] = 0;

			}

		}

		res *= res.Pow(m - 1 - now);

		printf("Case %d: %lld\n", ++kcase, res.val[0][n - 1]);

	}

    return 0;

}