// Slower C++ solution:
#include <cstdio>

#include <vector>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <map>

using namespace std;



typedef long long LL;

const int maxn = 75, MOD = 1000000009;



int n, N;

LL m;

map<LL, vector<LL> > s;



class Matrix {

public:

	LL val[maxn][maxn];

	Matrix() {

		memset(val, 0, sizeof(val));

	}



	Matrix operator*(const Matrix& c) const {

		Matrix res;

		for (int i = 0; i < n; ++i)

			for (int j = 0; j < n; ++j)

				for (int k = 0; k < n; ++k) {

					res.val[i][j] += val[i][k] * c.val[k][j];

					res.val[i][j] = (res.val[i][j] + MOD) % MOD; //髦イ豁「遏ゥ髦オ蜈?エ?序荳コ雍滓焚?瑚凶荳埼怙隕?シ悟悉謗?+MOD"

				}

		return res;

	}



	Matrix& operator*=(const Matrix& c) {

		*this = *this * c;

		return *this;

	}



	Matrix Pow(LL k) { //霑泌屓one^k

		Matrix res = Zero();

		Matrix step = One();

		while (k) {

			if (k & 1)

				res *= step;

			k >>= 1;

			step *= step;

		}

		return res;

	}



	Matrix Zero() const {

		Matrix res;

		for (int i = 0; i < maxn; ++i)

			res.val[i][i] = 1;

		return res;

	}



	Matrix One() const {

		Matrix res;

		res.val[0][0] = res.val[0][1] = 1;

		res.val[n-1][n-1] = res.val[n-1][n-2] = 1;

		for (int i = 1; i < n - 1; ++i) {

			res.val[i][i-1] = res.val[i][i] = res.val[i][i + 1] = 1;

		}

		return res;

	}

};



int main() {

	int kcase = 0;

	while (scanf("%d%lld%d", &n, &m, &N) && n) {

		s.clear();

		for (int i = 0; i < N; ++i) {

			LL x, y;

			scanf("%lld%lld", &x, &y);

			s[--y].push_back(--x);

		}

		if (n == 1) {

			if (N) {

				printf("Case %d: 0\n", ++kcase);

			} else {

				printf("Case %d: 1\n", ++kcase);

			}

			continue;

		}

		Matrix res;

		res.val[0][0] = 1;

		LL now = 0;

		for (map<LL, vector<LL> >::iterator it = s.begin(); it != s.end(); ++it) {

			if (it -> first == 0) continue;

			res *= res.Pow((it -> first) - now);

			now = it -> first;

			for (int i = 0; i < (it -> second).size(); ++i) {

				res.val[0][(it -> second)[i]] = 0;

			}

		}

		res *= res.Pow(m - 1 - now);

		printf("Case %d: %lld\n", ++kcase, res.val[0][n - 1]);

	}

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7693378738565992x):
#include <bits/stdc++.h>



#define REP(i,n) for(int i=0;i<(int)(n);i++)

#define ALL(x) (x).begin(),(x).end()



using namespace std;



using ll = long long;

using ld = long double;



template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }



template<int M>

class Modulo {

  using ll = long long;

  int n;

public:

  Modulo () : n(0) {;}

  Modulo (int m) : n(m) {

    if (n >= M) n %= M;

    else if (n < 0) n = (n % M + M) % M;

  }

  Modulo (ll m) {

    if (m >= M) m %= M;

    else if (m < 0) m = (m % M + M) % M;

    n = m;

  }

  explicit operator int() const { return n; }

  explicit operator ll() const { return n; }

  bool operator==(const Modulo &a) const { return n == a.n; }

  Modulo operator+=(const Modulo &a) { n += a.n; if (n >= M) n -= M; return *this; }

  Modulo operator-=(const Modulo &a) { n -= a.n; if (n < 0) n += M; return *this; }

  Modulo operator*=(const Modulo &a) { n = (ll(n) * a.n) % M; return *this; }

  Modulo operator+(const Modulo &a) const { Modulo res = *this; return res += a; }

  Modulo operator-(const Modulo &a) const { Modulo res = *this; return res -= a; }

  Modulo operator*(const Modulo &a) const { Modulo res = *this; return res *= a; }

};



const int mod = 1000000009;



using Mod = Modulo<mod>;

template <typename T> using Matrix = vector<vector<T>>;



template<typename T>

T dot(const vector<T> &a, const vector<T> &b) {

  return inner_product(begin(a), end(a), begin(b), T(0));

}



template<typename T>

Matrix<T> transpose(const Matrix<T> &A) {

  const int n = A[0].size(), m = A.size();

  Matrix<T> res(n, vector<T>(m, 0));

  for (int i = 0; i < n; ++i)

    for (int j = 0; j < m; ++j)

      res[i][j] = A[j][i];

  return res;

}



template<typename T>

Matrix<T> operator*(const Matrix<T> &a, Matrix<T> b) {

  b = transpose(b);

  const int n = a.size(), m = b.size();

  assert (a[0].size() == b[0].size());

  Matrix<T> res(n, vector<T>(m));

  for (int i = 0; i < n; ++i)

    for (int j = 0; j < m; ++j)

      res[i][j] = dot(a[i], b[j]);

  return res;

}



template<typename T>

Matrix<T> powmat(const Matrix<T> &a, ll n) {

  if (n == 0) {

    const int n = a.size();

    Matrix<T> res(n, vector<T>(n, 0));

    REP(i,n) res[i][i] = Mod(1);

    return res;

  }

  else {

    if (n % 2) return powmat(a, n - 1) * a;

    return powmat(a * a, n / 2);

  }

}



int main() {

  ll W, H, N;

  for (int cas = 1; cin >> W >> H >> N, W; ++cas) {

    Matrix<Mod> next(W, vector<Mod>(W, 0));

    REP(i,W) REP(j,W) {

      if (abs(i - j) <= 1) next[i][j] = 1;

    }

    vector<pair<ll,ll>> obstacles;

    REP(i,N) {

      ll x, y;

      cin >> x >> y;

      obstacles.emplace_back(y - 1, x - 1);

    }

    sort(ALL(obstacles));

    Matrix<Mod> vec(W, vector<Mod>(1, 0));

    vec[0][0] = 1;

    ll prev = 0;

    for (auto p: obstacles) {

      ll y, x;

      tie(y, x) = p;

      vec = powmat(next, y - prev) * vec;

      vec[x][0] = 0;

      prev = y;

    }

    vec = powmat(next, H - 1 - prev) * vec;

    printf("Case %d: %d\n", cas, int(vec[W-1][0]));

  }

  return 0;

}