#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

typedef vector<long long> vec;
typedef vector<vec> mat;

constexpr long long MAX_LOG_H = 62;
constexpr long long mod = 1000000009;

mat F[MAX_LOG_H];

mat operator*(const mat &A, const mat &B) {
	const int n = A.size();
	const int m = B[0].size();

	mat C(n, vec(m, 0));

	for(int i = 0; i < n; ++i) {
		for(int k = 0; k < static_cast<int>(B.size()); ++k) {
			for(int j = 0; j < m; ++j) {
				C[i][j] += A[i][k] * B[k][j];
				if(C[i][j] >=  mod) C[i][j] %= mod;
			}
		}
	}

	return C;
}

void init(int w, long long h) {
	const int log_h = log2(h) + 1;

	F[0].assign(w, vec(w));
	for(int i = 0; i < w; ++i) {
		F[0][i][i] = 1;
		if(i) F[0][i][i - 1] = 1;
		if(i < w - 1) F[0][i][i + 1] = 1;
	}

	for(int i = 0; i < log_h; ++i) {
		F[i + 1] = F[i] * F[i];
	}
}

mat calc(int n, long long k) {
	mat res(n, vec(n));
	for(int i = 0; i < n; ++i) {
		res[i][i] = 1;
	}

	for(int i = 0; k > 0; ++i) {
		if(k & 1) res = move(res) * F[i];
		k >>= 1;
	}

	return res;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int w, n;
	long long h;

	for(int case_number = 1; cin >> w >> h >> n && w; ++case_number) {
		init(w, h);

		map<long long, vector<int>> ng;
		for(int i = 0; i < n; ++i) {
			int x;
			long long y;
			cin >> x >> y;
			ng[y].emplace_back(x - 1);
		}

		mat ans(1, vec(w, 0));
		ans[0][0] = 1;

		long long prev = 1;
		for(auto it = ng.cbegin(); it != ng.cend(); ++it) {
			ans = calc(w, it->first - prev) * move(ans);

			for(const auto &x : it->second) {
				ans[x][0] = 0;
			}

			prev = it->first;
		}

		ans = calc(w, h - prev) * move(ans);

		cout << "Case " << case_number << ": " << ans[w - 1][0] << endl;
	}

	return EXIT_SUCCESS;
}