Problem: There is a grid that consists of W \times H cells. The upper-left-most cell is (1, 1). You are standing on the cell of (1,1) and you are going to move to cell of (W, H). You can only move to adjacent lower-left, lower or lower-right cells.

There are obstructions on several cells. You can not move to it. You cannot move out the grid, either. Write a program that outputs the number of ways to reach (W,H) modulo 1,000,000,009. You can assume that there is no obstruction at (1,1).



Input

The first line contains three integers, the width W, the height H, and the number of obstructions N. (1 \leq W \leq 75, 2 \leq H \leq 10^{18}, 0 \leq N \leq 30) Each of following N lines contains 2 integers, denoting the position of an obstruction (x_i, y_i).

The last test case is followed by a line containing three zeros.

Output

For each test case, print its case number and the number of ways to reach (W,H) modulo 1,000,000,009.

Example

Input

2 4 1
2 1
2 2 1
2 2
0 0 0


Output

Case 1: 4
Case 2: 0

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;



const int mod = 1000000009;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

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

#define MAX_MOD_N 1024000

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


namespace detail {

	bool is_zero(double d) {
		return (std::abs(d) < 1e-9);
	}
	bool is_zero(long double d) {
		return (std::abs(d) < 1e-9);
	}

}

template <typename T>
class matrix {
public:
	matrix() = delete;
	matrix(int r, int c)
		: v_(r, std::vector<T>(c)),
		row_(r),
		column_(c)
	{}
	matrix(std::vector<std::vector<T>> const& v)
		: v_(v),
		row_(v.size()),
		column_((v.size() == 0 ? 0 : v[0].size()))
	{}
	matrix(matrix const&) = default;
	matrix(matrix&&) = default;
	matrix& operator=(matrix const&) = default;
	matrix& operator=(matrix&&) = default;
	~matrix() = default;

	std::vector<T>& operator[](unsigned int i) {
		return v_[i];
	}
	const std::vector<T>& operator[](unsigned int i) const {
		return v_[i];
	}
	matrix& operator+=(matrix const& other) {
		assert("matrix operator+: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

		for (int i = 0; i<row_; ++i) {
			for (int j = 0; j<column_; ++j) {
				v_[i][j] += other[i][j];
			}
		}
		return *this;
	}
	matrix& operator-=(matrix const& other) {
		assert("matrix operator-: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

		for (int i = 0; i<row_; ++i) {
			for (int j = 0; j<column_; ++j) {
				v_[i][j] -= other[i][j];
			}
		}
		return *this;
	}

	bool operator==(matrix const& rhs) const {
		if (row_ != rhs.row_size() || column_ != rhs.column_size()) {
			return false;
		}
		for (int i = 0; i<row_; ++i) {
			for (int j = 0; j<column_; ++j) {
				if (std::abs(v_[i][j] - rhs[i][j]) > 1e-9) {
					return false;
				}
			}
		}
		return true;
	}
	bool operator!=(matrix const& rhs) {
		return !(*this == rhs);
	}

	int row_size() const {
		return row_;
	}
	int column_size() const {
		return column_;
	}

	// for debug
	void print() {
		for (int i = 0; i<row_; ++i) {
			for (int j = 0; j<column_; ++j) {
				std::cout << v_[i][j];
				if (j != column_ - 1) {
					std::cout << " ";
				}
			}
			std::cout << std::endl;
		}
	}

private:
	std::vector<std::vector<T>> v_;
	int row_, column_;
};

template <typename T>
matrix<T> operator-(matrix<T> m) {
	for (int i = 0; i<m.row_size(); ++i) {
		for (int j = 0; j<m.column_size(); ++j) {
			m[i][j] = -m[i][j];
		}
	}
}

template <typename T>
matrix<T> operator+(matrix<T> lhs, matrix<T> const& rhs) {
	lhs += rhs;
	return lhs;
}

template <typename T>
matrix<T> operator-(matrix<T> lhs, matrix<T> const& rhs) {
	lhs -= rhs;
	return lhs;
}

template <typename T>
matrix <T> operator*(matrix<T> const& lhs, matrix<T> const& rhs) {
	assert("matrix operator*: lhs.column_size() != rhs.row_size()" && lhs.column_size() == rhs.row_size());

	matrix<T> ret(lhs.row_size(), rhs.column_size());
	for (int i = 0; i<ret.row_size(); ++i) {
		for (int k = 0; k<lhs.column_size(); ++k) {
			for (int j = 0; j<ret.column_size(); ++j) {
				ret[i][j] += lhs[i][k] * rhs[k][j];
			}
		}
	}
	return ret;
}

template <typename T>
matrix<T> transpose(matrix<T> const& m) {
	const int R = m.row_size(), C = m.column_size();
	matrix<T> ret(C, R);
	for (int i = 0; i<C; ++i) {
		for (int j = 0; j<R; ++j) {
			ret[i][j] = m[j][i];
		}
	}
	return ret;
}

// verified
template <typename T>
int rank_matrix(matrix<T> a) {
	const int r = a.row_size(), c = a.column_size();
	matrix<long double> b(r, c);
	for (int i = 0; i<r; ++i) {
		for (int j = 0; j<c; ++j) {
			b[i][j] = static_cast<long double>(a[i][j]);
		}
	}
	return rank_matrix<long double>(std::move(b));
}

template <>
int rank_matrix(matrix<long double> a) {
	const int R = a.row_size(), C = a.column_size();
	int r = 0;
	for (int i = 0; i<C && r < R; ++i) {
		int pivot = r;
		for (int j = r + 1; j<R; ++j) {
			if (std::abs(a[j][i]) > std::abs(a[pivot][i])) {
				pivot = j;
			}
		}
		std::swap(a[pivot], a[r]);
		if (detail::is_zero(a[r][i])) {
			continue;
		}
		for (int k = C - 1; k >= i; --k) {
			a[r][k] = a[r][k] / a[r][i];
		}
		for (int j = r + 1; j<R; ++j) {
			for (int k = C - 1; k >= i; --k) {
				a[j][k] += -a[r][k] * a[j][i];
			}
		}
		++r;
	}
	return r;
}

// todo: only long double?
template <typename T>
T det(matrix<T> a) {
	const int R = a.row_size(), C = a.column_size();
	matrix<long double> b(R, C);
	for (int i = 0; i<R; ++i) {
		for (int j = 0; j<C; ++j) {
			b[i][j] = static_cast<long double>(a[i][j]);
		}
	}
	return static_cast<T>(det<long double>(std::move(b)));
}
template <>
long double det(matrix<long double> a) {
	assert("det(): matrix is not square." && a.column_size() == a.row_size());
	const int R = a.row_size(), C = a.column_size();
	long double ret = 1.0;
	for (int i = 0; i<R; ++i) {
		int pivot = i;
		for (int j = i + 1; j<R; ++j) {
			if (std::abs(a[j][i]) > std::abs(a[pivot][i])) {
				pivot = j;
			}
		}
		std::swap(a[pivot], a[i]);
		ret *= a[i][i] * (i != pivot ? -1.0 : 1.0);
		if (detail::is_zero(a[i][i])) {
			break;
		}
		for (int j = i + 1; j<R; ++j) {
			for (int k = C - 1; k >= i; --k) {
				a[j][k] -= a[i][k] * a[j][i] / a[i][i];
			}
		}
	}
	return ret;
}

template <typename T>
matrix<T> eye(int n) {
	matrix<T> res(n, n);
	for (int i = 0; i<n; ++i) {
		res[i][i] = 1;
	}
	return res;
}

// mulptile mod ver
template <typename T>
matrix<T> mul(matrix<T> const& a, matrix<T> const& b, long long M) {
	int R = a.row_size(), C = b.column_size();
	assert("matrix mul: row and column size does not match" && a.column_size() == b.row_size());
	matrix<T> ret(R, C);
	for (int i = 0; i<R; ++i) {
		for (int k = 0; k<a.column_size(); ++k) {
			for (int j = 0; j<C; ++j) {
				ret[i][j] = (ret[i][j] + ((a[i][k] * b[k][j]) % M)) % M;
			}
		}
	}
	return ret;
}

template <typename T>
matrix<T> pow(matrix<T> x, long long y) {
	assert("matrix pow: matrix is not square" && x.column_size() == x.row_size());
	matrix<T> ret = eye<T>(x.column_size());
	while (y > 0) {
		if (y & 1) {
			ret = ret * x;
		}
		x = x * x;
		y >>= 1;
	}
	return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long y, long long M) {
	assert("matrix pow: matrix is not square" && x.column_size() == x.row_size());
	matrix<T> ret = eye<T>(x.column_size());
	while (y > 0) {
		if (y & 1) {
			ret = mul(ret, x, M);
		}
		x = mul(x, x, M);
		y >>= 1;
	}
	return ret;
}



// LUP factorization(gauss)
// verified
// Ax = b
// note: A must be regular(non-singular)
// return: x
//         or size 0 vector (if x does not exist or not unique)
vector<double> gauss_jordan(matrix<double>& A, std::vector<double> const& b) {
	int n = A.row_size();
	matrix<double> B(n, n + 1);
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<n; ++j) {
			B[i][j] = A[i][j];
		}
	}
	for (int i = 0; i<n; ++i) {
		B[i][n] = b[i];
	}

	for (int i = 0; i<n; ++i) {
		int pivot = i;
		for (int j = i; j<n; ++j) {
			if (std::abs(B[j][i]) > std::abs(B[pivot][i])) {
				pivot = j;
			}
		}
		std::swap(B[i], B[pivot]);
		if (std::abs(B[i][i]) < 1e-9) {
			return std::vector<double>();
		}

		for (int j = i + 1; j <= n; ++j) {
			B[i][j] /= B[i][i];
		}
		for (int j = 0; j<n; ++j) {
			if (i != j) {
				for (int k = i + 1; k <= n; ++k) {
					B[j][k] -= B[j][i] * B[i][k];
				}
			}
		}
	}

	std::vector<double> x(n);
	for (int i = 0; i<n; ++i) {
		x[i] = B[i][n];
	}
	return x;
}


struct lu_data {
	matrix<double> A;
	std::vector<int> pi;
};

// LU decomposition 
// A = LU
// A: n * n
// Verified
lu_data lu_decomposition(matrix<double> A) {
	std::vector<int> pi;
	const int n = A.row_size();
	for (int i = 0; i<n; ++i) {
		int pivot = i;
		for (int j = i + 1; j<n; ++j) {
			if (std::fabs(A[pivot][i]) < std::fabs(A[j][i])) {
				pivot = j;
			}
		}
		pi.push_back(pivot);
		std::swap(A[pivot], A[i]);
		for (int j = i + 1; j<n; ++j) {
			for (int k = i + 1; k<n; ++k) {
				A[j][k] -= A[i][k] * A[j][i] / A[i][i];
			}
			A[j][i] /= A[i][i];
		}
	}
	return lu_data{ A, pi };
}

// solve Ax = LUx = b
std::vector<double> lu_solve(lu_data LU, std::vector<double> b) {
	matrix<double>& A = LU.A;
	std::vector<int> &pi = LU.pi;
	const int n = A.row_size();
	for (int i = 0; i<(int)pi.size(); ++i) {
		std::swap(b[i], b[pi[i]]);
	}
	// set c = Ux
	// solve Lc = b
	// (assign: b[i] <- c[i])
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<i; ++j) {
			b[i] -= A[i][j] * b[j];
		}
	}
	// solve Ux = c
	for (int i = n - 1; i >= 0; --i) {
		for (int j = i + 1; j<n; ++j) {
			b[i] -= A[i][j] * b[j];
		}
		b[i] /= A[i][i];
	}
	return b;
}

int main() {
	int casenum = 0;
	while (1) {
		casenum++;
		int W, N; long long int H; cin >> W >> H >> N;
		if (!W)break;
		map<long long int, vector<int>>mp;
		//vector<vector<Mod>>forspaces(W, vector<Mod>(W));
		matrix<Mod> forspaces(W, W);
		for (int y = 0; y < W; ++y) {
			for (int x = 0; x < W; ++x) {
				if (abs(x - y) <= 1)forspaces[y][x] = true;
			}
		}
		bool flag = true;
		for (int i = 0; i < N; ++i) {
			int x; long long  y; cin >> x >> y;
			x--; y--;
			if (!x&&!y) {
				flag = false;
			}
			mp[y].push_back(x);
		}
		Mod ans = 0;
		if (flag) {
			for (int i = 0; i < W - 1; ++i) {
				mp[H - 1].push_back(i);
			}
			//vector<vector<Mod>>nums(W, vector<Mod>(1));
			matrix<Mod>nums(W, 1);
			nums[0][0] = 1;
			long long int nowy = 0;
			for (auto it = mp.begin(); it != mp.end(); ++it) {
				long long int nexty = it->first;
				vector<int>obs(it->second);
				if (nexty == nowy)continue;
				else {
					long long int spaces = nexty - nowy - 1;
					nums=pow(forspaces, spaces)*nums;
					//nums = keisann(powgyou(forspaces, spaces), nums);

					matrix<Mod> forobs(forspaces);
					for (int y = 0; y < W; ++y) {
						for (int x = 0; x < W; ++x) {
							if (find(obs.begin(), obs.end(), y) != obs.end())forobs[y][x] = false;
						}
					}
					nums = forobs*nums;
					nowy = nexty;
				}
			}
			ans = nums[W - 1][0];
		}

		cout << "Case " << casenum << ": " << ans.num << endl;
	}
	return 0;
}