Problem:
Three-way Branch 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. Sample Input 2 4 1
2 1
2 2 1
2 2
0 0 0 Output for the Sample Input Case 1: 4
Case 2: 0

Solution (Python):
from collections import defaultdict
import sys
readline = sys.stdin.readline
write = sys.stdout.write

MOD = 10**9 + 9

def matmul(N, A, B):
    C = [[0]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(N)) % MOD
    return C

def prepare(N, H):
    mat = [[0]*N for i in range(N)]
    res = []
    for i in range(N):
        mat[i][i] = 1
    res.append([e[:] for e in mat])
    for i in range(N-1):
        mat[i][i+1] = mat[i+1][i] = 1
    res.append([e[:] for e in mat])
    while H:
        mat = matmul(N, mat, mat)
        res.append([e[:] for e in mat])
        H >>= 1
    return res
def matpow(X, N, h, MS):
    k = 1
    while h:
        if h & 1:
            mat = MS[k]
            X = [sum(ai*xi for ai, xi in zip(mat_i, X)) % MOD for mat_i in mat]
        h >>= 1
        k += 1
    return X

cnt = 1
def solve():
    W, H, N = map(int, readline().split())
    if W == H == N == 0:
        return False
    P = defaultdict(list)
    for i in range(N):
        x, y = map(int, readline().split())
        if y > 1:
            P[y-1].append(x-1)
    MS = prepare(W, H)
    *S, = P.items()
    S.sort()
    X = [0]*W
    X[0] = 1
    prv = 0
    for y, vs in S:
        X = matpow(X, W, y-prv, MS)
        for v in vs:
            X[v] = 0
        prv = y
    if prv < H-1:
        X = matpow(X, W, H-1-prv, MS)
    write("Case %d: %d\n" % (cnt, X[W-1]))
    return True
while solve():
    cnt += 1

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+9
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Matrix():
    def __init__(self, A):
        self.A = A
        self.row = len(A)
        self.col = len(A[0])

    def __iter__(self):
        return self.A.__iter__()

    def __getitem__(self, i):
        return self.A.__getitem__(i)

    def __add__(self, B):
        aa = self.A
        bb = B.A
        return Matrix([[aa[i][j] + bb[i][j] for j in range(self.col)] for i in range(self.row)])

    def __sub__(self, B):
        aa = self.A
        bb = B.A
        return Matrix([[aa[i][j] - bb[i][j] for j in range(self.col)] for i in range(self.row)])

    def __mul__(self, B):
        bb = [[B.A[j][i] for j in range(B.row)] for i in range(B.col)]
        return Matrix([[sum([ak * bk for ak,bk in zip(ai,bj)]) % mod for bj in bb] for ai in self.A])

    def __truediv__(self, x):
        pass

    def pow_init(self, a):
        self.PA = pa = {}
        t = self.pow(a[0])
        c = a[0]
        pa[c] = t
        for d in a[1:]:
            t = t * self.pow(d-c)
            pa[d] = t
            c = d

    def pow(self, n):
        if n in self.PA:
            return self.PA[n]
        A = self
        r = Matrix([[0 if j != i else 1 for j in range(self.row)] for i in range(self.row)])
        while n > 0:
            if n % 2 == 1:
                r = r * A
            A = A * A
            n //= 2
        return r

    def __str__(self):
        return self.A.__str__()

def main():
    rr = []

    def f(w,h,n):
        a = sorted([LI()[::-1] for _ in range(n)])
        aa = [[0]*w for _ in range(w)]
        for i in range(w):
            ai = aa[i]
            ai[i] = 1
            if i > 0:
                ai[i-1] = 1
            if i < w-1:
                ai[i+1] = 1
        A = Matrix(aa)
        A.pow_init(list(map(lambda x: x[0], a)) + [h])
        t = [[0] for _ in range(w)]
        t[0][0] = 1
        T = Matrix(t)
        c = 1
        for hi,wi in a:
            T = A.pow(hi-c) * T
            T.A[wi-1][0] = 0
            c = hi
        T = A.pow(h-c) * T
        return T.A[-1][0]

    ci = 0
    while 1:
        ci += 1
        n,m,l = LI()
        if n == 0:
            break
        rr.append('Case {}: {}'.format(ci, f(n,m,l)))

    return '\n'.join(map(str, rr))


print(main())