#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define MOD 1000000009


struct Info{
	bool operator<(const struct Info &arg) const{
		return row < arg.row;
	}
	ll row;
	vector<int> V;
};


typedef vector<ll> V;
typedef vector<V> MATRIX;

int num_obstacle;
int N,case_num = 1;
int W,info_index;
ll H;
Info info[30];

MATRIX calc_ans(MATRIX left, MATRIX right){
    MATRIX RET(1,V(N));
    for(int col = 0; col < N; col++){
    	RET[0][col] = 0;
    	for(int row = 0; row < N; row++){
    		RET[0][col] += left[0][row]*right[row][col];
    		RET[0][col] %= MOD;
    	}
    }

    return RET;
}


MATRIX calc(MATRIX left,MATRIX right){

	MATRIX ret(N,V(N));

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++)ret[i][k] = 0;
	}

	for(int row = 0; row < N; row++){
		for(int col = 0; col < N; col++){
			for(int a = 0; a < N; a++){
				ret[row][col] += left[row][a]*right[a][col];
				ret[row][col] %= MOD;
			}
		}
	}

	return ret;
}


MATRIX pow(MATRIX MULT,ll count){

	if(count == 1){
		return MULT;
	}

	MATRIX ret(N,V(N));

	for(int row = 0; row < N; row++){
		for(int col = 0; col < N; col++){
			if(row == col)ret[row][col] = 1;
			else{
				ret[row][col] = 0;
			}
		}
	}

	while(count > 0){
		if(count%2 == 1)ret = calc(ret,MULT);
		MULT = calc(MULT,MULT);
		count /= 2;
	}

	return ret;
}


void func(){

	for(int i = 0; i < num_obstacle; i++){
		info[i].V.clear();
	}

	info_index = 0;
	N = W;

	int tmp_col;
	ll tmp_row;
	bool FLG;

	for(int loop = 0; loop < num_obstacle; loop++){

		scanf("%d %lld",&tmp_col,&tmp_row);
		tmp_col--;
		tmp_row--;

		if(tmp_row == 0)continue;

		FLG = false;

		for(int i = 0; i < info_index; i++){
			if(info[i].row == tmp_row){
				info[i].V.push_back(tmp_col);
				FLG = true;
				break;
			}
		}

		if(!FLG){
			info[info_index].row = tmp_row;
			info[info_index].V.push_back(tmp_col);

			info_index++;
		}
	}

	sort(info,info+info_index);

	MATRIX ans(1,V(W)),work(1,V(W));
	ans[0][0] = 1;
	for(int col = 1; col < W; col++)ans[0][col] = 0;

	MATRIX POWER(W,V(W)),WORK_POWER(W,V(W));

	for(int row = 0; row < W; row++){
		for(int col = 0; col < W; col++)POWER[row][col] = 0;
	}

	for(int col = 0; col < W; col++){
		for(int diff = -1; diff <= 1; diff++){
			if(col+diff < 0 || col+diff >= W)continue;
			POWER[col][col+diff]++;
		}
	}

	ll current_row = 0,next_row;

	for(int i = 0; i < info_index; i++){
		next_row  = info[i].row;

		WORK_POWER = pow(POWER,(next_row)-current_row);
		ans = calc_ans(ans,WORK_POWER);

		for(int k = 0; k < info[i].V.size(); k++){
			ans[0][info[i].V[k]] = 0;
		}

		current_row = next_row;
	}

	if((H-1)-current_row >= 1){
		WORK_POWER = pow(POWER,(H-1)-current_row);
		ans = calc_ans(ans,WORK_POWER);
	}

	printf("Case %d: %lld\n",case_num++,ans[0][W-1]%MOD);
}


int main(){

	while(true){
		scanf("%d %lld %d",&W,&H,&num_obstacle);
		if(W == 0 && H == 0 && num_obstacle == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 3252