// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

#define MOD 1000000009

long long w,h,n;

struct Matrix{

    long long n,m[80][80];

    Matrix  operator * (const Matrix &b)const{

        Matrix c;

        memset(c.m,0,sizeof c.m);

        c.n=n;

        for (int i=0;i<n;i++)

        for (int j=0;j<n;j++)

        for (int k=0;k<n;k++){

            c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%MOD)%MOD;

        }

        return c;

    }

};

Matrix ones;

Matrix Pow(const Matrix &a,unsigned long long n){

    Matrix t=ones,y=a;

    while (n){

        if (n & 1) t = (t * y) ;

        y = (y * y) ;

        n /= 2;

    }

    return t;

}

Matrix A;

long long x[80];

long long k,p,q;

struct node{

    long long a,b;

};

node Pos[80];

int cmp(node a,node b){

    return a.b<b.b;

}

void get_x(Matrix a){

    long long y[80];

    memset(y,0,sizeof y);

    for (int i=0;i<a.n;i++){

        for (int j=0;j<a.n;j++){

            y[i]=(y[i]+(x[j]*a.m[i][j])%MOD)%MOD;

        }

    }

    for (int i=0;i<a.n;i++)

        x[i]=y[i];

}

int main(){

    int i,j;

    int d=0;

    while (scanf("%lld%lld%lld",&w,&h,&n)!=EOF){

        memset(ones.m,0,sizeof ones.m);

        for (i=0;i<w;i++)

            ones.m[i][i]=1;

        ones.n=w;

        for (i=0;i<n;i++)

            scanf("%lld%lld",&Pos[i].a,&Pos[i].b);

        sort(Pos,Pos+n,cmp);

        if ((w==0)&&(h==0)&&(n==0)) return 0;

        memset(x,0,sizeof x);

        x[0]=1;

        memset(A.m,0,sizeof A.m);

        A.n=w;

        A.m[0][0]=1;

        A.m[0][1]=1;

        for (i=1;i<w;i++){

            A.m[i][i]=1;

            A.m[i][i-1]=1;

            A.m[i][i+1]=1;

        }

        k=0;

        j=0;

        while (j<n){

            p=Pos[j].b-1;

            if (p==k){

                x[Pos[j].a-1]=0;

            }

            else{

                get_x(Pow(A,p-k));

                k=p;

                x[Pos[j].a-1]=0;

            }

            j++;

        }

        if (k<h-1){

            get_x(Pow(A,h-1-k));

        }

        printf("Case %d: %lld\n",++d,x[w-1]);

    }

}

// Faster C++ solution for the same problem (measured speedup: 2.266257916396459x):
#include <bits/stdc++.h>



#define REP(i,n) for(int i=0;i<(int)(n);i++)

#define ALL(x) (x).begin(),(x).end()



using namespace std;



using ll = long long;

using ld = long double;



template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }



template<int M>

class Modulo {

  using ll = long long;

  int n;

public:

  Modulo () : n(0) {;}

  Modulo (int m) : n(m) {

    if (n >= M) n %= M;

    else if (n < 0) n = (n % M + M) % M;

  }

  Modulo (ll m) {

    if (m >= M) m %= M;

    else if (m < 0) m = (m % M + M) % M;

    n = m;

  }

  explicit operator int() const { return n; }

  explicit operator ll() const { return n; }

  bool operator==(const Modulo &a) const { return n == a.n; }

  Modulo operator+=(const Modulo &a) { n += a.n; if (n >= M) n -= M; return *this; }

  Modulo operator-=(const Modulo &a) { n -= a.n; if (n < 0) n += M; return *this; }

  Modulo operator*=(const Modulo &a) { n = (ll(n) * a.n) % M; return *this; }

  Modulo operator+(const Modulo &a) const { Modulo res = *this; return res += a; }

  Modulo operator-(const Modulo &a) const { Modulo res = *this; return res -= a; }

  Modulo operator*(const Modulo &a) const { Modulo res = *this; return res *= a; }

};



const int mod = 1000000009;



using Mod = Modulo<mod>;

template <typename T> using Matrix = vector<vector<T>>;



template<typename T>

T dot(const vector<T> &a, const vector<T> &b) {

  return inner_product(begin(a), end(a), begin(b), T(0));

}



template<typename T>

Matrix<T> transpose(const Matrix<T> &A) {

  const int n = A[0].size(), m = A.size();

  Matrix<T> res(n, vector<T>(m, 0));

  for (int i = 0; i < n; ++i)

    for (int j = 0; j < m; ++j)

      res[i][j] = A[j][i];

  return res;

}



template<typename T>

Matrix<T> operator*(const Matrix<T> &a, Matrix<T> b) {

  b = transpose(b);

  const int n = a.size(), m = b.size();

  assert (a[0].size() == b[0].size());

  Matrix<T> res(n, vector<T>(m));

  for (int i = 0; i < n; ++i)

    for (int j = 0; j < m; ++j)

      res[i][j] = dot(a[i], b[j]);

  return res;

}



template<typename T>

Matrix<T> powmat(const Matrix<T> &a, ll n) {

  if (n == 0) {

    const int n = a.size();

    Matrix<T> res(n, vector<T>(n, 0));

    REP(i,n) res[i][i] = Mod(1);

    return res;

  }

  else {

    if (n % 2) return powmat(a, n - 1) * a;

    return powmat(a * a, n / 2);

  }

}



int main() {

  ll W, H, N;

  for (int cas = 1; cin >> W >> H >> N, W; ++cas) {

    Matrix<Mod> next(W, vector<Mod>(W, 0));

    REP(i,W) REP(j,W) {

      if (abs(i - j) <= 1) next[i][j] = 1;

    }

    vector<pair<ll,ll>> obstacles;

    REP(i,N) {

      ll x, y;

      cin >> x >> y;

      obstacles.emplace_back(y - 1, x - 1);

    }

    sort(ALL(obstacles));

    Matrix<Mod> vec(W, vector<Mod>(1, 0));

    vec[0][0] = 1;

    ll prev = 0;

    for (auto p: obstacles) {

      ll y, x;

      tie(y, x) = p;

      vec = powmat(next, y - prev) * vec;

      vec[x][0] = 0;

      prev = y;

    }

    vec = powmat(next, H - 1 - prev) * vec;

    printf("Case %d: %d\n", cas, int(vec[W-1][0]));

  }

  return 0;

}