#include "bits/stdc++.h"

using namespace std;

using ll = long long;

ll h, w, n;
int cs = 1;

template <typename T>
using matrix = std::vector<std::vector<T>>;

constexpr long long mod = 1e9+9;

template <typename T>
matrix<T> modmul(const matrix<T> &l, const matrix<T> &r)
{
    matrix<T> ret(l.size(), std::vector<T>(r[0].size()));
    for (int i = 0; i < (int)l.size(); i++)
    {
        for (int k = 0; k < (int)r.size(); k++)
        {
            for (int j = 0; j < (int)r[0].size(); j++)
            {
                ret[i][j] += l[i][k] * r[k][j] % mod;
                ret[i][j] %= mod;
            }
        }
    }
    return ret;
}

template <typename T>
std::vector<T> modmul(const matrix<T> &a, const std::vector<T> &x)
{
    const int n = a.size();
    const int m = x.size();
    std::vector<T> ret(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ret[i] += a[i][j] * x[j] % mod;
            ret[i] %= mod;
        }
    }
    return ret;
}

template <typename T>
matrix<T> eye(const int n)
{
    matrix<T> ret(n, std::vector<T>(n));
    for (int i = 0; i < n; i++)
        ret[i][i] = 1;
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long n)
{
    auto ret = eye<T>(x.size());
    while (n)
    {
        if (n & 1)
            ret = modmul(ret, x);
        x = modmul(x, x);
        n /= 2;
    }
    return ret;
}


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

    while (cin >> w >> h >> n, h || w || n)
    {
        cout << "Case " << cs << ": ";
        cs++;
        bool f = false;
        set<ll> st = {h};
        map<ll, vector<ll>> mp;
        for (int i = 0; i < n; i++)
        {
            ll x, y;
            cin >> y >> x;
            if (x == 1)
                continue;
            st.insert(x);
            y--;
            mp[x].push_back(y);
            if (x == h && y == w)
            {
                f = true;
            }
        }
        if (f)
        {
            cout << 0 << endl;
            continue;
        }
        vector<vector<ll>> id(w, vector<ll>(w, 0));
        for (int i = 0; i < w; i++)
        {
            id[i][i] = 1;
            if (i)
                id[i][i - 1] = 1;
            if (i + 1 < w)
                id[i][i + 1] = 1;
        }
        vector<ll> x(w, 0);
        x[0] = 1;
        ll pre = 1;
        for (auto v : st)
        {
            x = modmul(modpow(id, v - pre), x);
            for (auto y : mp[v])
                x[y] = 0;
            pre = v;
        }
        cout << x[w - 1] << endl;
    }
}

