import java.lang.Math.*
fun main(args:Array<String>?): Unit {
    var case = 1
    while(true) {
        val (w, h, n) = readLine()!!.trim().split(' ')
        if (w == "0" && h == "0" && n == "0") return
        val width = w.toInt()
        val height = h.toLong()
        val coordinates = Array(n.toInt()){
            val (x, y) = readLine()!!.trim().split(' ')
            Coordinate(x.toInt(), y.toLong())
        }.groupBy(Coordinate::y).toList().sortedBy(Pair<Long, List<Coordinate>>::first).dropWhile{it.first == 1L}
        var initial = LongArray(width){0L}
        initial[0] = 1
        var current = 1L
        for ((y, coords) in coordinates){
            val block = BooleanArray(width){false}
            for ((x, _) in coords) block[x - 1] = true
            initial = move(move(initial, y - current - 1), block)
            current = y
        }
        if (current != height) initial = move(initial, height - current)
        println("Case ${case++}: ${initial.last()}")
    }
}
data class Coordinate(val x: Int, val y: Long)
const val mod = 1_000_000_009L
fun multiple(left: LongArray, right: Array<LongArray>): LongArray {
    val result = LongArray(right.first().size){0L}
    for (i in result.indices) for (j in right.indices){
        result[i] += left[j] * right[j][i]
        result[i] %= mod
    }
    return result
}
fun multiple(left: Array<LongArray>, right: Array<LongArray>): Array<LongArray> {
    val result = Array(left.size){LongArray(right.first().size){0L}}
    for (i in result.indices) for (j in result[i].indices){
        for (k in left[i].indices) {
            result[i][j] += left[i][k] * right[k][j]
            result[i][j] %= mod
        }
    }
    return result
}
fun pow2(base: Array<LongArray>): Array<LongArray> = multiple(base, base)
fun pow(base: Array<LongArray>, exp: Long): Array<LongArray> {
    if (exp == 0L) return (Array(base.size){r -> LongArray(base.size){if (it == r) 1L else 0L}})
    if (exp == 1L) return base
    if (exp % 2 == 0L) return pow2(pow(base, exp / 2))
    else return multiple(base, pow(base, exp - 1))
}
fun moveMatrix(h: Long, w: Int): Array<LongArray> {
    val base = Array(w){i -> LongArray(w){if (abs(it - i) <= 1) 1L else 0}}
    return pow(base, h)
}
fun move(line: LongArray, h: Long): LongArray {
    return if (h == 0L) line
    else multiple(line, moveMatrix(h, line.size))
}
fun move(line: LongArray, block: BooleanArray): LongArray {
    val result = LongArray(line.size){0L}
    for (i in result.indices){
        if (!block[i]) for (j in -1 .. 1) if (i + j in line.indices){
            result[i] += line[i + j]
        }
        result[i] %= mod
    }
    return result
}
