#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);++i)
#define rep2(i,a,b) for (int i=(a);i<(b);++i)
#define rrep(i,n) for (int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;--i)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1e9;
const int mod = 1e9 + 9;
using Graph = vector<vector<int>>;

using Vec = vector<int>;
using Mat = vector<Vec>;

Mat mulMatMat(const Mat& a, const Mat& b) {
    int n = a.size();
    int m = b[0].size();
    assert(a[0].size() == b.size());
    Mat c(n, Vec(m, 0));
    rep(i, n) {
        rep(j, m) {
            rep(k, a[0].size()) {
                (c[i][j] += (a[i][k] * b[k][j]) % mod) %= mod;
            }
        }
    }
    return c;
}

void addMatMat(Mat& a, const Mat& b) {
    assert(a.size() == b.size());
    assert(a[0].size() == b[0].size());
    rep(i, a.size()) {
        rep(j, a[0].size()) {
            (a[i][j] += b[i][j]) %= mod;
        }
    }
}

Vec mulMatVec(const Mat& a, const Vec& v) {
    int n = a.size();
    assert(a[0].size() == v.size());
    Vec c(n, 0);
    rep(i, n) {
        rep(j, a[0].size()) {
            (c[i] += a[i][j] * v[j]) %= mod;
        }
    }
    return c;
}


main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int w, h, n;
    int testcase = 0;
    while (cin >> w >> h >> n, w) {
        testcase++;

        map<int, vi> mp;
        rep(i, n) {
            int c, r;
            cin >> c >> r;
            c--; r--;
            mp[r].emplace_back(c);
        }
        mp[h - 1];

        // if (testcase != 8) continue;

        Mat A(w, Vec(w, 0));
        rep(i, w) {
            for (int j = max(0ll, i - 1); j <= min(w - 1, i + 1); j++) {
                A[i][j] = 1;
            }
        }

        Vec v(w, 0);
        v[0] = 1;

        int c = 0;
        for (auto p : mp) {
            int nc; vi vr;
            tie(nc, vr) = p;

            // output(nc); printV(vr);

            if (nc == c) continue;

            Mat B = A;
            for (int i = nc - c; i > 0; i >>= 1) {
                if (i & 1) {
                    v = mulMatVec(B, v);
                }
                B = mulMatMat(B, B);
                // printVV(B);
            }

            // printV(v);

            // Mat C = A;
            // for (auto i : vr) {
            //     for (int j = max(0ll, i - 1); j <= min(w - 1, i + 1); j++) {
            //         C[i][j] = 0;
            //     }
            // }
            // // printVV(C);
            // v = mulMatVec(C, v);
            //
            // printV(v);

            for (auto i : vr) {
                v[i] = 0;
            }

            // printV(v);

            c = nc;
        }

        cout << "Case " << testcase << ": " << v.back() << endl;
    }
}

Measured memory_bytes: 3332