#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const int MOD = 1000000009;

template <typename T>
class Matrix {

private:
	int N, M;
	vector< vector<T> > data;

	template <typename _Func>
	Matrix<T> apply(_Func f) const {
		Matrix<T> ret(N, M);
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < M; ++j){ ret(i, j) = f(data[i][j]); }
		}
		return ret;
	}

	template <typename _Func>
	Matrix<T> apply_scalar(const T &s, _Func f) const { return apply(bind2nd(f, s)); }

	template <typename _Func>
	Matrix<T> apply_mat(const Matrix<T> &m, _Func f) const {
		assert(N == m.N && M == m.M);
		Matrix<T> ret(N, M);
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < M; ++j){ ret(i, j) = f(data[i][j], m(i, j)); }
		}
		return ret;
	}

public:
	Matrix(int N, int M) : N(N), M(M), data(N, vector<T>(M)) { }
	int rows() const { return N; }
	int columns() const { return M; }
	const T &operator()(int i, int j) const { return data[i][j]; }
	T &operator()(int i, int j){ return data[i][j]; }
	Matrix<T> operator-() const { return apply(negate<T>()); }
	Matrix<T> operator+(const T &s) const { return apply_scalar(s, plus<T>()); }
	Matrix<T> &operator+=(const T &s){ return *this = *this + s; }
	Matrix<T> operator-(const T &s) const { return apply_scalar(s, minus<T>()); }
	Matrix<T> &operator-=(const T &s){ return *this = *this - s; }
	Matrix<T> operator*(const T &s) const { return apply_scalar(s, multiplies<T>()); }
	Matrix<T> &operator*=(const T &s){ return *this = *this * s; }
	Matrix<T> operator/(const T &s) const { return apply_scalar(s, divides<T>()); }
	Matrix<T> &operator/=(const T &s){ return *this = *this / s; }
	Matrix<T> operator%(const T &s) const { return apply_scalar(s, modulus<T>()); }
	Matrix<T> &operator%=(const T &s){ return *this = *this % s; }
	Matrix<T> operator+(const Matrix<T> &m) const { return apply_mat(m, plus<T>()); }
	Matrix<T> &operator+=(const Matrix<T> &m){ return *this = *this + m; }
	Matrix<T> operator-(const Matrix<T> &m) const { return apply_mat(m, minus<T>()); }
	Matrix<T> &operator-=(const Matrix<T> &m){ return *this = *this - m; }
	Matrix<T> operator*(const Matrix<T> &m) const {
		assert(M == m.N);
		Matrix<T> ret(N, m.M);
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < m.M; ++j){
				for(int k = 0; k < M; ++k){ ret(i, j) += data[i][k] * m(k, j); }
			}
		}
		return ret;
	}
	Matrix<T> &operator*=(const Matrix<T> &m){ return *this = *this * m; }

	Matrix<T> modmul(const Matrix<T> &m, T mod) const {
		assert(M == m.N);
		Matrix<T> ret(N, m.M);
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < m.M; ++j){
				for(int k = 0; k < M; ++k){
					ret(i, j) = (ret(i, j) + data[i][k] * m(k, j)) % mod;
				}
			}
		}
		return ret;
	}
};

Matrix<ll> modpow(Matrix<ll> a, ll e){
	const int n = a.rows();
	Matrix<ll> retval(n, n);
	for(int i = 0; i < n; ++i){ retval(i, i) = 1; }
	while(e > 0){
		if(e & 1){ retval = retval.modmul(a, MOD); }
		a = a.modmul(a, MOD);
		e >>= 1;
	}
	return retval;
}

int main(){
	ios_base::sync_with_stdio(false);
	for(int caseNum = 1; true; ++caseNum){
		ll w, h, n;
		cin >> w >> h >> n;
		if(w == 0 && h == 0 && n == 0){ break; }
		vector<pii> objs(n);
		for(int i = 0; i < n; ++i){
			cin >> objs[i].second >> objs[i].first;
			--objs[i].first; --objs[i].second;
		}
		sort(objs.begin(), objs.end());
		Matrix<ll> skip(w, w);
		for(int i = 0; i < w; ++i){
			skip(i, i) = 1;
			if(i > 0){ skip(i - 1, i) = 1; }
			if(i < w - 1){ skip(i + 1, i) = 1; }
		}
		Matrix<ll> current(w, 1);
		current(0, 0) = 1;
		ll prev_row = 0;
		for(int i = 0; i < n; ){
			const ll cur_row = objs[i].first;
			const Matrix<ll> a = modpow(skip, cur_row - prev_row);
			current = a.modmul(current, MOD);
			for(; i < n && objs[i].first == cur_row; ++i){
				current(objs[i].second, 0) = 0;
			}
			prev_row = cur_row;
		}
		const Matrix<ll> a = modpow(skip, h - prev_row - 1);
		current = a.modmul(current, MOD);
		cout << "Case " << caseNum << ": " << current(w - 1, 0) << endl;
	}
	return 0;
}

Measured memory_bytes: 1416