#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <complex>
#include <cmath>
#include <algorithm>
#include <valarray>

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

template<ll MD>
struct SMatrix {
    typedef ll D;
    vector<valarray<D>> d;
    SMatrix() {}
    int N, M;
    SMatrix(int n, int m) {
        N = n; M = m;
        d.resize(n);
        for (int i = 0; i < N; i++) {
            d[i] = valarray<D>(D(0), m);
        }
    }
    valarray<D>& operator[](int p) {
        return d[p];
    }
    const valarray<D>& operator[](int p) const {
        return d[p];
    }

    SMatrix operator*(const SMatrix &right) {
        assert(M == right.N);
        SMatrix res(N, right.M), r(right.M, right.N);
        for (int i = 0; i < right.M; i++) {
            for (int j = 0; j < right.N; j++) {
                r[i][j] = right[j][i];
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < right.M; j++) {
                res[i][j] = (d[i]*r[j]%MD).sum()%MD;
            }
        }
        return res;
    }

    SMatrix pow(ll p) {
        assert(N == M);
        SMatrix res(N, M), buf = *this;
        for (int i = 0; i < N; i++) {
            res[i][i] = D(1);
        }
        while (p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }
};

const ll MD = 1e9+9;

SMatrix<MD> res;

ll w;
void mul(ll x) {
    SMatrix<MD> p(w, w);

    for (int i = 0; i < w; i++) {
        for (int j = -1; j <= 1; j++) {
            if (i+j < 0) continue;
            if (w <= i+j) continue;
            p[i][i+j] = 1;
        }
    }
    p = p.pow(x);

    res = p * res;
}

bool solve(int ca) {
    ll h, n;
    cin >> w >> h >> n;
    if (!w) return false;
    res = SMatrix<MD>(w, 1);
    vector<P> v;
    vector<ll> u;
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y; x--; y--;
        v.push_back(P(x, y));
        u.push_back(y);
    }
    u.push_back(0);
    u.push_back(h-1);
    sort(u.begin(), u.end());
    res[0][0] = 1;
    for (int i = 1; i < (int)u.size(); i++) {
        mul(u[i]-u[i-1]);
        for (P p: v) {
            if (p.second != u[i]) continue;
            res[p.first] = 0;
        }
    }
    printf("Case %d: %lld\n", ca, res[w-1][0]);
    return true;
}

int main() {
    int ca = 1;
    while (true) {
        if (!solve(ca)) break;
        ca++;
    }
    return 0;
}