#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isIn(x,y,h,w) (x >= 0 && x < h && y >= 0 && y < w)

#define int long long
//using ll = long long;
using P = pair<int,int>;

ostream &operator<<(ostream &os,const P &p){ return os << "(" << p.first << "," << p.second << ")"; }

template<class T> T &chmin(T &a,const T &b){ return a = min(a,b); }
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000009;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod; 
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};

template<class T>
struct Matrix{
	vector<vector<T>> A;
	Matrix(int n) : A(n,vector<T>(n,T(0))){}
	Matrix(int n,int m) : A(n,vector<T>(m,T(0))){}

	int size() const{ return A.size(); }
	vector<T> &operator[](const int k){ return A[k]; }
	const vector<T> &operator[](const int k) const{ return A[k]; }
	Matrix operator*(const T &x) const{ Matrix(*this) *= x; }
	Matrix operator*(const Matrix &B) const{ Matrix(*this) *= B; }
	
	Matrix &operator*=(const T &x){
		for(int i = 0;i < A.size();i++){
			for(int j = 0;j < A[0].size();j++) A[i][j] *= x;
		}
		return *this;
	}

	Matrix &operator*=(const Matrix &B) {
		assert(A[0].size() == B.size());
		vector<vector<T>> C(A.size(),vector<T>(B[0].size(),T(0)));
		for(int i = 0;i < A.size();i++){
			for(int k = 0;k < B.size();k++){
				for(int j = 0;j < B[0].size();j++) C[i][j] += A[i][k] * B[k][j];
			}
		}
		A.swap(C);
		return *this;
	}

	vector<T> operator*(const vector<T> &v) const{
		assert(A[0].size() == v.size());
		vector<T> ret(A.size());
		for(int i = 0;i < A.size();i++){
			for(int j = 0;j < A[0].size();j++) ret[i] += A[i][j] * v[j];
		}
		return ret;
	}

	Matrix pow(long long x) const{
		assert(A.size() == A[0].size());
		Matrix ret = E(A.size()),tmp = *this;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}

	static Matrix E(int n){
		Matrix ret(n);
		for(int i = 0;i < n;i++) ret[i][i] = T(1);
		return ret;
	}
};

void solve(int w,int h,int n){
	vector<P> vec;
	for(int i = 0;i < n;i++){
		int x,y;
		cin >> y >> x; y--;x--;
		vec.emplace_back(x,y);
	}
	vec.emplace_back(0,0);
	vec.emplace_back(h - 1,-1);
	sort(all(vec));
	vector<modint<MOD>> v(w);
	v[0] = 1;
	Matrix<modint<MOD>> A(w);
	for(int i = 0;i < w;i++){
		for(int j = -1;j <= 1;j++){
			if(i + j >= 0 && i + j < w) A[i][i + j] = 1;
		}
	}
	for(int i = 1;i < vec.size();i++){
		v = A.pow(vec[i].first - vec[i - 1].first) * v;
		if(vec[i].second != -1) v[vec[i].second] = 0;
	}
	cout << v[w - 1] << endl;
}

signed main(){
	int w,h,n;
	for(int t = 1;;t++){
		cin >> w >> h >> n;
		if(!w) break;
		printf("Case %lld: ",t);
		solve(w,h,n);
	}
}


Measured memory_bytes: 3368