#include<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<set>
using namespace std;

#include<assert.h>
const int mod = 1000000009;

struct Mod {
	int num;
	Mod() : num(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) { ; }
	Mod(int n) : num((n % mod + mod) % mod) { ; }
	operator int() { return num; }
};

Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(long long int a, Mod b) { return Mod(a) + b; }
Mod operator-(Mod a, Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(long long int a, Mod b) { return Mod(a) - b; }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(long long int a, Mod b) { return Mod(a)*b; }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator+=(long long int &a, Mod b) { return a = a + b; }
Mod operator-=(Mod &a, Mod b) { return a = a - b; }
Mod operator-=(long long int &a, Mod b) { return a = a - b; }
Mod operator*=(Mod &a, Mod b) { return a = a * b; }
Mod operator*=(long long int &a, Mod b) { return a = a * b; }
Mod operator^(Mod a, int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod inv(Mod a) { return a ^ (mod - 2); }
Mod operator/(Mod a, Mod b) {
	assert(b != 0);
	return a * inv(b);
}
Mod operator/(long long int a, Mod b) {
	assert(b != 0);
	return Mod(a) * inv(b);
}

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(int a, int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}


vector<vector<Mod>> keisann(const vector<vector<Mod>>l, const vector<vector<Mod>>r) {
	vector<vector<long long int>> ll(l.size(),vector<long long int>(l[0].size())), rr(r.size(), vector<long long int>(r[0].size()));
	for (int i = 0; i < l.size(); ++i) {
		for (int j = 0; j < l[0].size(); ++j){
			ll[i][j] = l[i][j].num;
		}
	}
	for (int i = 0; i < r.size(); ++i) {
		for (int j = 0; j < r[0].size(); ++j) {
			rr[i][j] = r[i][j].num;
		}
	}
	vector<vector<Mod>>ans(l.size(), vector<Mod>(r[0].size()));
	assert(l[0].size() == r.size());
	for (int h = 0; h < l.size(); ++h) {
		for (int w = 0; w < r[0].size(); ++w) {
			long long int aa=0;
			for (int i = 0; i < r.size(); ++i) {

				aa+= (ll[h][i] * rr[i][w])%mod;
				//ans[h][w] += l[h][i] * r[i][w];
			}
			ans[h][w] = aa%mod;
		}
	}
	return ans;
}

vector<vector<Mod>>powgyou(vector<vector<Mod>>a, const long long int n) {
	assert(a.size() == a[0].size());
	if (n == 0) {
		vector<vector<Mod>>ans(a);
		for (int i = 0; i < ans.size(); ++i) {
			for (int j = 0; j < ans.size(); ++j) {
				ans[i][j] = 0;
			}
		}
		for (int i = 0; i < ans.size(); ++i) {
			ans[i][i] = 1;
		}
		return ans;
	}
	if (n == 1)return a;
	else {
		vector<vector<Mod>>ans(a.size(), vector<Mod>(a[0].size(), 0));
		ans = powgyou(a, n / 2);
		ans = keisann(ans, ans);
		if (n % 2) {
			ans = keisann(ans, a);
		}
		return ans;
		
	}
}
//#define FOR(i,a,b) for(int i=(a);i<(b);++i)
//#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
//class segtree
//{
//public:
//	vector<int> seg;
//	int size;
//	segtree(int n)
//	{
//		size = 1;
//		while (size < n)  size *= 2;
//		seg.resize(size * 2, -1);
//	}
//
//	void update(int k, int v)
//	{
//		k += size - 1;
//		seg[k] = v;
//		while (k > 0)
//		{
//			k = (k - 1) / 2;
//			seg[k] = min(seg[k * 2 + 1], seg[k * 2 + 2]);
//		}
//	}
//
//	int query(int v)
//	{
//		int k = 0;
//		while (k < size - 1)
//		{
//			if (seg[k * 2 + 1] < v)
//			{
//				k = k * 2 + 1;
//			}
//			else
//			{
//				k = k * 2 + 2;
//			}
//		}
//		return k - (size - 1);
//	}
//};


int main()
{
	int i = 0;
	while (1) {
		i++;
		long long int W, H, N; cin >> W >> H >> N;
		if (!W)break;
		map<long long int, vector<int >>bs;
		for (int i = 0; i < N; ++i) {
			long long int x, y; cin >> x >> y; x--; y--;
			bs[y].push_back(x);
		}

		long long int pre = 0;
		vector<vector<Mod>>gyou(W, vector<Mod>(1, 0));
		gyou[0][0] = 1;

		vector<vector<Mod>>Kakeru(W, vector<Mod>(W));
		for (int i = 0; i < W; ++i) {
			for (int j = 0; j < W; ++j) {
				if (abs(i - j) <= 1) {
					Kakeru[i][j] = Mod(1);
				}
			}
		}

		for (auto it = bs.begin(); it != bs.end(); ++it) {
			if (it->first == 0) {
				continue;
			}
			else {
				vector<vector<Mod>>a(powgyou(Kakeru, (*it).first - pre));
				vector<vector<Mod>>b(keisann(a, gyou));
				vector<int>c((*it).second);
				for (int j = 0; j < c.size(); ++j) {
					b[c[j]][0] = 0;
				}
				gyou = b;
				pre = (*it).first;
			}
		}

		vector<vector<Mod>>a(powgyou(Kakeru, H-1 - pre));
		vector<vector<Mod>>b(keisann(a, gyou));

		Mod ans = b[W - 1][0];
		cout << "Case " << i << ": " << ans << endl;
	}
	
	return 0;
	
}

Measured memory_bytes: 14112