Problem: There is a grid that consists of W \times H cells. The upper-left-most cell is (1, 1). You are standing on the cell of (1,1) and you are going to move to cell of (W, H). You can only move to adjacent lower-left, lower or lower-right cells.

There are obstructions on several cells. You can not move to it. You cannot move out the grid, either. Write a program that outputs the number of ways to reach (W,H) modulo 1,000,000,009. You can assume that there is no obstruction at (1,1).



Input

The first line contains three integers, the width W, the height H, and the number of obstructions N. (1 \leq W \leq 75, 2 \leq H \leq 10^{18}, 0 \leq N \leq 30) Each of following N lines contains 2 integers, denoting the position of an obstruction (x_i, y_i).

The last test case is followed by a line containing three zeros.

Output

For each test case, print its case number and the number of ways to reach (W,H) modulo 1,000,000,009.

Example

Input

2 4 1
2 1
2 2 1
2 2
0 0 0


Output

Case 1: 4
Case 2: 0

Solution (in CPP):

Solution:
#include <cassert>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

using P = pair<long, long>;

namespace detail {

bool is_zero(double d) {
    return (std::abs(d) < 1e-9);
}
bool is_zero(long double d) {
    return (std::abs(d) < 1e-9);
}

}

template <typename T>
class matrix {
public:
    matrix() = delete;
    matrix(int r, int c) 
        : v_(r, std::vector<T>(c)),
          row_(r),
          column_(c)
    {}
    matrix(std::vector<std::vector<T>> const& v)
        : v_(v),
          row_(v.size()),
          column_((v.size() == 0 ? 0 : v[0].size()))
    {}
    matrix(matrix const&) = default;
    matrix(matrix&&) = default;
    matrix& operator=(matrix const&) = default;
    matrix& operator=(matrix&&) = default;
    ~matrix() = default;

    std::vector<T>& operator[](unsigned int i) {
        return v_[i];
    }
    const std::vector<T>& operator[](unsigned int i) const {
        return v_[i];
    }
    matrix& operator+=(matrix const& other) {
        assert("matrix operator+: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                v_[i][j] += other[i][j];
            }
        }
        return *this;
    }
    matrix& operator-=(matrix const& other) {
        assert("matrix operator-: row or column size does not match" && other.row_size() == row_ && other.column_size() == column_);

        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                v_[i][j] -= other[i][j];
            }
        }
        return *this;
    }

    bool operator==(matrix const& rhs) const {
        if(row_ != rhs.row_size() || column_ != rhs.column_size()) {
            return false;
        }
        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                if(std::abs(v_[i][j] - rhs[i][j]) > 1e-9) {
                    return false;
                }
            }
        }
        return true;
    }
    bool operator!=(matrix const& rhs) {
        return !(*this == rhs);
    }

    int row_size() const {
        return row_;
    }
    int column_size() const {
        return column_;
    }

    // for debug
    void print() {
        for(int i=0; i<row_; ++i) {
            for(int j=0; j<column_; ++j) {
                std::cout << v_[i][j];
                if(j != column_ - 1) {
                    std::cout << " ";
                }
            }
            std::cout << std::endl;
        }
    }

private:
    std::vector<std::vector<T>> v_;
    int row_, column_;
};

template <typename T>
matrix<T> operator-(matrix<T> m) {
    for(int i=0; i<m.row_size(); ++i) {
        for(int j=0; j<m.column_size(); ++j) {
            m[i][j] = -m[i][j];
        }
    }
}

template <typename T>
matrix<T> operator+(matrix<T> lhs, matrix<T> const& rhs) {
    lhs += rhs;
    return lhs;
}

template <typename T>
matrix<T> operator-(matrix<T> lhs, matrix<T> const& rhs) {
    lhs -= rhs;
    return lhs;
}

template <typename T>
matrix <T> operator*(matrix<T> const& lhs, matrix<T> const& rhs) {
    assert("matrix operator*: lhs.column_size() != rhs.row_size()" && lhs.column_size() == rhs.row_size());

    matrix<T> ret(lhs.row_size(), rhs.column_size());
    for(int i=0; i<ret.row_size(); ++i) {
        for(int k=0; k<lhs.column_size(); ++k) {
            for(int j=0; j<ret.column_size(); ++j) {
                ret[i][j] += lhs[i][k] * rhs[k][j];
            }
        }
    }
    return ret;
}

template <typename T>
matrix<T> transpose(matrix<T> const& m) {
    const int R = m.row_size(), C = m.column_size();
    matrix<T> ret(C, R);
    for(int i=0; i<C; ++i) {
        for(int j=0; j<R; ++j) {
            ret[i][j] = m[j][i];
        }
    }
    return ret;
}

// verified
template <typename T>
int rank_matrix(matrix<T> a) {
    const int r = a.row_size(), c = a.column_size();
    matrix<long double> b(r, c);
    for(int i=0; i<r; ++i) {
        for(int j=0; j<c; ++j) {
            b[i][j] = static_cast<long double>(a[i][j]);
        }
    }
    return rank_matrix<long double>(std::move(b));
}

template <>
int rank_matrix(matrix<long double> a) {
    const int R = a.row_size(), C = a.column_size();
    int r = 0;
    for(int i=0; i<C && r < R; ++i) {
        int pivot = r;
        for(int j=r+1; j<R; ++j) {
            if(std::abs(a[j][i]) > std::abs(a[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(a[pivot], a[r]);
        if(detail::is_zero(a[r][i])) {
            continue;
        }
        for(int k=C-1; k>=i; --k) {
            a[r][k] = a[r][k] / a[r][i];
        }
        for(int j=r+1; j<R; ++j) {
            for(int k=C-1; k>=i; --k) {
                a[j][k] += -a[r][k] * a[j][i];
            }
        }
        ++r;
    }
    return r;
}

// todo: only long double?
template <typename T>
T det(matrix<T> a) {
    const int R = a.row_size(), C = a.column_size();
    matrix<long double> b(R, C);
    for(int i=0; i<R; ++i) {
        for(int j=0; j<C; ++j) {
            b[i][j] = static_cast<long double>(a[i][j]);
        }
    }
    return static_cast<T>(det<long double>(std::move(b)));
}
template <>
long double det(matrix<long double> a) {
    assert("det(): matrix is not square." && a.column_size() == a.row_size());
    const int R = a.row_size(), C = a.column_size();
    long double ret = 1.0;
    for(int i=0; i<R; ++i) {
        int pivot = i;
        for(int j=i+1; j<R; ++j) {
            if(std::abs(a[j][i]) > std::abs(a[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(a[pivot], a[i]);
        ret *= a[i][i] * (i != pivot ? -1.0 : 1.0);
        if(detail::is_zero(a[i][i])) {
            break;
        }
        for(int j=i+1; j<R; ++j) {
            for(int k=C-1; k>=i; --k) {
                a[j][k] -= a[i][k] * a[j][i] / a[i][i];
            }
        }
    }
    return ret;
}

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

// mulptile mod ver
template <typename T>
matrix<T> mul(matrix<T> const& a, matrix<T> const& b) {
    int R = a.row_size(), C = b.column_size();
    matrix<T> ret(R, C);
    for(int i=0; i<R; ++i) {
        for(int k=0; k<a.column_size(); ++k) {
            for(int j=0; j<C; ++j) {
                ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % (int)(1e9+9);
            }
        }
    }
    return ret;
}

template <typename T>
matrix<T> pow(matrix<T> x, long long y) {
    assert("matrix pow: matrix is not square" && x.column_size() == x.row_size());
    matrix<T> ret = eye<T>(x.column_size());
    while(y > 0) {
        if(y & 1) {
            ret = ret * x;
        }
        x = x * x;
        y >>= 1;
    }
    return ret;
}

template <typename T>
matrix<T> modpow(matrix<T> x, long long y) {
    matrix<T> ret = eye<T>(x.column_size());
    while(y > 0) {
        if(y & 1) {
            ret = mul(ret, x);
        }
        x = mul(x, x);
        y >>= 1;
    }
    return ret;
}



// LUP factorization(gauss)
// verified
// Ax = b
// note: A must be regular(non-singular)
// return: x
//         or size 0 vector (if x does not exist or not unique)
vector<double> gauss_jordan(matrix<double>& A, std::vector<double> const& b) {
    int n = A.row_size();
    matrix<double> B(n, n+1);
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            B[i][j] = A[i][j];
        }
    }
    for(int i=0; i<n; ++i) {
        B[i][n] = b[i];
    }

    for(int i=0; i<n; ++i) {
        int pivot = i;
        for(int j=i; j<n; ++j) {
            if(std::abs(B[j][i]) > std::abs(B[pivot][i])) {
                pivot = j;
            }
        }
        std::swap(B[i], B[pivot]);
        if(std::abs(B[i][i]) < 1e-9) {
            return std::vector<double>();
        }

        for(int j=i+1; j<=n; ++j) {
            B[i][j] /= B[i][i];
        }
        for(int j=0; j<n; ++j) {
            if(i != j) {
                for(int k=i+1; k<=n; ++k) {
                    B[j][k] -= B[j][i] * B[i][k];
                }
            }
        }
    }

    std::vector<double> x(n);
    for(int i=0; i<n; ++i) {
        x[i] = B[i][n];
    }
    return x;
}


struct lu_data {
    matrix<double> A;
    std::vector<int> pi;
};

// LU decomposition 
// A = LU
// A: n * n
// Verified
lu_data lu_decomposition(matrix<double> A) {
    std::vector<int> pi;
    const int n = A.row_size();
    for(int i=0; i<n; ++i) {
        int pivot = i;
        for(int j=i+1; j<n; ++j) {
            if(std::fabs(A[pivot][i]) < std::fabs(A[j][i])) {
                pivot = j;
            }
        }
        pi.push_back(pivot);
        std::swap(A[pivot], A[i]);
        for(int j=i+1; j<n; ++j) {
            for(int k=i+1; k<n; ++k) {
                A[j][k] -= A[i][k] * A[j][i] / A[i][i];
            }
            A[j][i] /= A[i][i];
        }
    }
    return lu_data{A, pi};
}

// solve Ax = LUx = b
std::vector<double> lu_solve(lu_data LU, std::vector<double> b) {
    matrix<double>& A = LU.A;
    std::vector<int> &pi = LU.pi;
    const int n = A.row_size();
    for(int i=0; i<(int)pi.size(); ++i) {
        std::swap(b[i], b[pi[i]]);
    }
    // set c = Ux
    // solve Lc = b
    // (assign: b[i] <- c[i])
    for(int i=0; i<n; ++i) {
        for(int j=0; j<i; ++j) {
            b[i] -= A[i][j] * b[j];
        }
    }
    // solve Ux = c
    for(int i=n-1; i>=0; --i) {
        for(int j=i+1; j<n; ++j) {
            b[i] -= A[i][j] * b[j];
        }
        b[i] /= A[i][i];
    }
    return b;
}

constexpr int mod = 1e9+9;
using ll = long long;

int main() {
    ll w, h, n;
    ll case_cnt = 0;
    while(cin >> w >> h >> n, w) {
        case_cnt++;
        matrix<ll> A(w, w);
        for(int i=0; i<w; ++i) {
            for(int j=0; j<3; ++j) {
                if(0 <= i+j-1 && i+j-1 < w) {
                    A[i][i+j-1] = 1;
                }
            }
        }
        matrix<ll> b(w, 1);
        b[0][0] = 1;
        vector<P> v;
        for(int i=0; i<n; ++i) {
            ll x, y;
            cin >> x >> y;
            x--; y--;
            if(y == 0) {
                continue;
            }
            v.push_back(make_pair(y, x));
        }
        ll cnt = 0;
        sort(v.begin(), v.end());
        matrix<ll> res = eye<ll>(w);
        for(int i=0; i<v.size(); ++i) {
            vector<ll> x = {v[i].second};
            ll y = v[i].first;
            for(int j=i+1; j<v.size(); ++j) {
                if(v[j].first == y) {
                    x.push_back(v[j].second);
                    if(j == v.size()-1) {
                        i = v.size()-1;
                    }
                } else {
                    i = j-1;
                    break;
                }
            }
            if(y-cnt-1 != 0) {
                res = mul(modpow(A, y-cnt-1), res);
            }
            matrix<ll> tmp = A;
            for(int j=0; j<x.size(); ++j) {
                for(int k=0; k<w; ++k) {
                    tmp[x[j]][k] = 0;
                }
            }
            res = mul(tmp, res);
            cnt = y;
        }
        if(h-cnt-1 != 0) {
            res = mul(modpow(A, h-cnt-1), res);
        }
        res = res * b;
        cout << "Case " << case_cnt << ": " << res[w-1][0] << endl;
    }
}