import std.stdio;
import std.ascii;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.random;
import std.regex;
import std.typecons;

int T = 0; // test case number 

int W;
long H;
int N;

struct Point {
    long x, y;
}

Point[] ps;

const long MOD = 1000000009;
final class Matrix {
    int H, W;
    long[][] M;
    this(int H, int W) {
        this.H = H; this.W = W;
        M = new long[][](H, W);
    }
    /*
    ref long[] opIndex(size_t index) {
        return M[index];
    }
    ref const(long[]) opIndex(size_t index) const {
        return M[index];
    }
    */
    override string toString() const {
        string ret;
        foreach (i; 0 .. H) {
            ret ~= format("%s\n", M[i]);
        }
        return ret;
    }
    Matrix opBinary(string op)(in Matrix X) const {
        static if (op == "+") {
            assert(H == X.H && W == X.W);
            auto ret = new Matrix(H, W);
            foreach (i, ref L; ret.M) {
                foreach (j, ref C; L) {
                    C = (M[i][j] + X.M[i][j]);
                    if (C >= MOD) C -= MOD;
                }
            }
            return ret;
        } else if (op == "*") {
            assert(W == X.H);
            auto ret = new Matrix(H, X.W);
            foreach (i, ref L; ret.M) {
                foreach (j, ref C; L) {
                    foreach (k; 0 .. W) {
                        C += M[i][k] * X.M[k][j] % MOD; 
                    }
                    C %= MOD;
                }
            }
            return ret;
        }
    }
    /* 蜊倅ス崎。悟?繧定ソ斐☆. 豁」譁ケ陦悟?縺ァ縺ェ縺代ｌ縺ーassert縺ォ蠑輔▲縺九°繧? */
    Matrix E() const {
        assert(H == W);
        auto ret = new Matrix(H, H);
        foreach (i; 0 .. H) { ret.M[i][i] = 1; }
        return ret;
    }
    Matrix opBinary(string op)(long x) const {
        static if (op == "^^") {
            if (x == 0) return E;
            if (x & 1) {
                return this ^^ (x - 1);
            } else {
                return (this * this) ^^ (x / 2);
            }
        }
    }
}

bool input() {
    scanf("%d %lld %d\n", &W, &H, &N);
    if (W == 0) return false;
    ps.destroy;
    foreach (i; 0 .. N) {
        long x, y;
        scanf("%lld %lld\n", &x, &y);
        x--; y--;
        ps ~= Point(y, x); /* 蜿崎サ「縺輔○繧? 蜈・蜉帙?邵ヲ髟キ縺?¢縺ゥ讓ェ髟キ縺ョ縺サ縺?′閠?∴繧?☆縺? */
    }
    ps.sort!"a.x < b.x";
    return true;
}

void solve() {
    auto M = new Matrix(W, W);
    foreach (int i; 0 .. W) {
        for (int d = -1; d <= 1; d++) {
            int p = i + d;
            if (p < 0 || p >= W) continue;
            M.M[p][i] = 1;
        }
    }
    auto V = new Matrix(W, 1);
    V.M[0][0] = 1;
    long prev = 0;

    static Matrix[64][76] cache;
    Matrix pow(Matrix M, long x) {
        if (cache[W][0] is null) cache[W][0] = M;
        auto ret = M.E;
        for (int i = 0; x > 0; i++) {
            if (cache[W][i] is null) cache[W][i] = cache[W][i - 1] * cache[W][i - 1];
            if (x & 1) ret = ret * cache[W][i];
            x >>= 1;
        }
        return ret;
    }

    for (int i = 0; i < N; ) {
        int from = i;
        V = pow(M, (ps[from].x - prev)) * V;
        while (i < N && ps[i].x == ps[from].x) {
            V.M[ps[i].y][0] = 0;
            i++; 
        }
        prev = ps[from].x;
    }
    if (prev < H - 1) { V = pow(M, (H - 1 - prev)) * V; }
    if (prev == H - 1) {
        foreach (i; 0 .. N) {
            if (ps[i].x == H - 1) {
                V.M[ps[i].y][0] = 0;
            }
        }
    }
    writeln("Case ", T, ": ", V.M[W - 1][0]);
}

void main() {
    while (input) {
        T++;
        solve;
    }
}