Three-way Branch

There is a grid of $W$ columns and $H$ rows. The upper left cell is $(1, 1)$: the first coordinate grows to the right and the second coordinate grows downward. You stand on $(1, 1)$ and you want to reach $(W, H)$.

From cell $(x, y)$ you may move only to the cell below and to the left $(x - 1, y + 1)$, the cell directly below $(x, y + 1)$, or the cell below and to the right $(x + 1, y + 1)$.

Some cells hold an obstruction. You cannot move onto an obstructed cell, and you cannot leave the grid. Write a program that prints the number of paths reaching $(W, H)$, modulo 1,000,000,009. The cell $(1, 1)$ never holds an obstruction.

The input holds several test cases.

The first line of each test case has the width $W$, the height $H$, and the number of obstructions $N$, separated by spaces. ($1 \le W \le 75$, $2 \le H \le 10^{18}$, $0 \le N \le 30$)

Each of the next $N$ lines has the position $x_i$, $y_i$ of one obstruction. ($1 \le x_i \le W$, $1 \le y_i \le H$)

The line after the last test case holds three zeros.

For each test case, print one line with the case number and the number of paths reaching $(W, H)$, modulo 1,000,000,009. If the answer of the $k$-th test case is $a$, print it in the form Case k: a.