#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const ll MOD = 1e9+9;

VL matvec(vector<VL> A, VL x){
    int n = x.size();
    VL y(n);
    REP(i,n) REP(j,n){
        y[i] = (y[i] + A[i][j] * x[j]) % MOD;
    }
    return y;
}

vector<VL> matprod(vector<VL> A, vector<VL> B){
    int n = A.size();
    vector<VL> C(n, VL(n));
    REP(i,n) REP(j,n) REP(k,n){
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    }
    return C;
}

vector<VL> matpow(vector<VL> A, ll p){
    int n = A.size();
    vector<VL> B(n, VL(n));
    REP(i,n) B[i][i] = 1;
    while (p){
        if (p & 1) B = matprod(B, A);
        A = matprod(A, A);
        p /= 2;
    }
    return B;
}

int main() {
    int w, n, t = 0;
    ll h;
    while (cin >> w >> h >> n && w){
        t++;
        printf("Case %d: ", t);
        vector<PL> p(n);
        REP(i,n){
            cin >> p[i].second >> p[i].first;
            p[i].first--;
            p[i].second--;
        }
        sort(p.begin(),p.end());
        VL a;
        a.push_back(0);
        REP(i,n){
            if (a[a.size()-1] != p[i].first)
                a.push_back(p[i].first);
        }
        a.push_back(h-1);
        int m = a.size();

        VL x(w);
        x[0] = 1;
        REP(i,m-1){
             vector<VL> A(w,VL(w));
             REP(k,w){
                A[k][k] = 1;
                A[k][min(w-1,k+1)] = 1;
                A[min(w-1,k+1)][k] = 1;
             }
             A = matpow(A, a[i+1]-a[i]);
             x = matvec(A, x);
             REP(j,n){
                if (p[j].first == a[i+1]) x[p[j].second] = 0;
             }
        }
        cout << x[w-1] << endl;
    }

    return 0;
}