#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;
typedef vector<vector<int64> > matrix;
const int64 mod = 1000000009LL;

matrix mul_matrix(const matrix &a, const matrix &b)
{
	const int l = a[0].size();
	const int m = a.size();
	const int r = b.size();

	matrix ret;

	ret.resize(r);
	for(int i = 0; i < r; ++i)
		ret[i].resize(l);

	for(int i = 0; i < r; ++i) {
		for(int j = 0; j < l; ++j) {
			for(int k = 0; k < m; ++k)
				ret[i][j] = (ret[i][j] + a[k][j] * b[i][k] % mod) % mod;
		}
	}

	return ret;
}

void pow_matrix_b(matrix &a, int64 x)
{
	matrix ret;
	const int n = a.size();

	ret.resize(n);
	for(int i = 0; i < n; ++i) {
		ret[i].resize(n, 0);
		ret[i][i] = 1;
	}

	for(int64 i = 1; i <= x; i *= 2) {
		if(i & x)
			ret = mul_matrix(ret, a);
		a = mul_matrix(a, a);
	}

	a = ret;
}

void fall(vector<int64> &v, int64 len)
{
	const int w = v.size();
	matrix f;

	f.resize(w);
	for(int i = 0; i < w; ++i)
		f[i].resize(w, 0);
	for(int i = 0; i < w; ++i) {
		for(int d = -1; d <= 1; ++d) {
			if(0 <= i + d && i + d < w)
				f[i+d][i] = 1;
		}
	}

	pow_matrix_b(f, len);

	matrix m, ret;

	m.push_back(v);
	ret = mul_matrix(f, m);
	v = ret[0];
}

int main()
{
	int case_count = 1;

	while(true) {

		int64 w, h;
		int n;
		vector<pair<int64, int64> > objs;
		vector<int64> v;
		vector<int64> ys;

		scanf("%lld%lld%d", &w, &h, &n);
		if(w == 0)
			break;
		objs.resize(n);
		for(int i = 0; i < n; ++i) {
			scanf("%lld%lld", &objs[i].first, &objs[i].second);
			objs[i].first -= 1; objs[i].second -= 1;
			ys.push_back(objs[i].second);
		}
		ys.push_back(h - 1);
		sort(ys.begin(), ys.end());
		ys.erase(unique(ys.begin(), ys.end()), ys.end());
		v.resize(w, 0);
		v[0] = 1;

		for(int step = 0; step < ys.size(); ++step) {
			int64 y = ys[step];
			int64 len = step > 0 ? y - ys[step - 1] : y;
			fall(v, len);
			for(int i = 0; i < n; ++i) {
				if(objs[i].second == y)
					v[objs[i].first] = 0;
			}
		}

		int64 ans = v[w - 1];
		printf("Case %d: %lld\n", case_count++, ans);
	}

	return 0;
}