Endless Knight (Large)

Chess has a piece called the knight. It does not move in a straight line like the other pieces, it jumps in an L shape. Precisely, a knight jumps from square $(r_1, c_1)$ to square $(r_2, c_2)$ if and only if $(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5$.

In this problem one knight has to cross a gigantic board of height $H$ and width $W$, from the top left square $(1, 1)$ to the bottom right square $(H, W)$.

The rules are these.

• The knight only moves right and down. Every jump lands on a square whose row number and column number are both larger. Because of that, the goal is sometimes unreachable. On a $3 \times 10$ board, for example, there is no way at all.
• $R$ squares of the board hold rocks. The knight may not land on such a square, although flying over one during a jump is allowed.

Count the distinct ways for the knight to go from $(1, 1)$ to $(H, W)$. Two ways are distinct when the sequence of squares the knight lands on differs. The count gets huge, so print its remainder modulo the prime 10007.

The first line contains a single integer $N$, the number of test cases. $N$ test cases follow.

The first line of each test case contains three integers $H$, $W$, and $R$. Each of the next $R$ lines contains two integers $r$ and $c$, the row number and the column number of one rock. Neither $(1, 1)$ nor $(H, W)$ holds a rock, and no two rocks share a square.

Limits

• $1 \le N \le 100$
• $0 \le R \le 10$
• $1 \le W \le 10^8$
• $1 \le H \le 10^8$
• $1 \le r \le H$
• $1 \le c \le W$

For each test case, print one line holding Case #X: followed by the number of ways to reach the goal square, taken modulo 10007. $X$ is the 1 based test case number.