#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

const ll M = 1000000009;

const int matrix_siz = 75;
struct sq_matrix{
	ll n;
	ll a[matrix_siz][matrix_siz];
	void init(int n_){
		n = n_;
		rep(i,n){
			rep(j,n){
				if(i == j)a[i][j] = 1;
				else a[i][j] = 0;
			}
		}
	}
	sq_matrix operator * (const sq_matrix y) {
		sq_matrix ret; ret.n = this->n;
		rep(i,this->n){
			rep(j,this->n){
				ret.a[i][j] = 0;
				rep(k,this->n){
					ret.a[i][j] += this->a[i][k] * y.a[k][j];
					ret.a[i][j] %= M;
				}
			}
		}
		return ret;
	}
};

sq_matrix sq_matrix_powers[62];
void sq_matrix_powers_init(sq_matrix x,int n){
	sq_matrix_powers[0] = x;
	rep1(i,61)sq_matrix_powers[i] = sq_matrix_powers[i-1]*sq_matrix_powers[i-1];
}
sq_matrix sq_matrix_pow(ll k){
	sq_matrix ret; ret.init(sq_matrix_powers[0].n);
	rep(i,61)if((k>>(ll)i)%2 == 1)ret = ret * sq_matrix_powers[i];
	return ret;
}

int main(){
	int test = 0;
	while(1){
		test ++;
		ll w,h,n;
		vector<P> vec;
		scanf("%lld%lld%lld",&w,&h,&n);
		if(w == 0)break;
		else printf("Case %d: ",test);
		rep(i,n){
			ll a,b;
			scanf("%lld%lld",&a,&b);
			if(b != 1)vec.pb( P(b,a-1) );
		}
		sor(vec);
		
		sq_matrix a; a.n = w;
		rep(i,w){
			rep(j,w){
				if(abs(i-j) <= 1)a.a[i][j] = 1;
				else a.a[i][j] = 0;
			}
		}
		sq_matrix_powers_init(a,w);
		sq_matrix ret; ret.init(w);
		ll loc = 1;
		rep(i,vec.size()){
			ret = ret*sq_matrix_pow(vec[i].fr-1-loc);
			loc = vec[i].fr;
			sq_matrix b = a;
			while(i < vec.size() && vec[i].fr == loc){
				rep(j,w)b.a[j][vec[i].sc] = 0;
				i ++;
			}
			i --;
			ret = ret*b;
		}
		ret = ret*sq_matrix_pow(h-loc);
		cout << ret.a[0][w-1] << endl;
	}
}
	