#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define all(x) begin(x),end(x)

#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 9;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


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

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

template<class T>
Matrix<T> pow(Matrix<T> a, ll k) {
    int n = a.size(), m = a[0].size();
    Matrix<T> ret(n, vector<T>(m));
    REP(i, n) ret[i][i] = 1;
    while (k) {
        if (k & 1) ret = ret * a;
        a = a * a; k >>= 1;
    }
    return ret;
}

struct modint {
    ll x;
    modint(ll x=0) : x(x) {}
    modint &operator+=(const modint& a) {
        (x += a.x) %= MOD;
        return *this;
    }
    friend modint operator*(const modint& a, const modint& b) {
        return modint((a.x * b.x) % MOD);
    }
    friend ostream &operator<<(ostream &os, const modint &a) {
        return os << a.x;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (int t = 1;; ++t) {
        ll W, H, N;
        cin >> W >> H >> N;
        if (W == 0) break;
        bool zero = false;
        map<ll, vi> obs;
        REP(i, N) {
            ll x, y;
            cin >> x >> y;
            --x, --y;
            if (x == 0 and y == 0) {
                zero = true;
            }
            if (y > 0) obs[y].emplace_back(x);
        }
        // for (auto tp : obs) debug(tp);
        // cerr << endl;
        if (zero) {
            cout << 0 << endl;
            return 0;
        }

        Matrix<modint> A(W, vector<modint>(W));
        REP(i, W) A[i][i] = 1;

        // REP(i, W) debug(A[i]);
        // cerr << endl;

        Matrix<modint> B = A;
        REP(i, W) {
            if (i - 1 >= 0) B[i][i - 1] = 1;
            if (i + 1 < W) B[i][i + 1] = 1;
        }
        // REP(i, W) debug(B[i]);
        // cerr << endl;

        ll prv = 0;
        for (auto &tp : obs) {
            ll now = tp.first;

            A = A * pow(B, now - prv - 1);
            // REP(i, W) debug(A[i]);
            // cerr << endl;

            Matrix<modint> tmp = B;
            for (int j : tp.second) {
                REP(i, W) tmp[i][j] = 0;
            }
            A = A * tmp;

            prv = now;

            // REP(i, W) debug(A[i]);
            // cerr << endl;
            // cerr << endl;
        }
        // debug(H - prv - 1);

        A = A * pow(B, H - prv - 1);
        // REP(i, W) debug(A[i]);
        // cerr << endl;

        // debug(A[0][W-1].x);
        cout << "Case " << t << ": " << A[0][W - 1].x << endl;
    }

    return 0;
}



Measured memory_bytes: 3296