P13473 [GCJ 2008 #3] Endless Knight

In the game of chess, there is a piece called the knight. A knight is special -- instead of moving in a straight line like other pieces, it jumps in an "L" shape. Specifically, a knight can jump from square $(r_1, c_1)$ to $(r_2, c_2)$ if and only if $(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5$. In this problem, one of our knights is going to undertake a chivalrous quest of moving from the top-left corner (the $(1, 1)$ square) to the bottom-right corner (the $(H, W)$ square) on a gigantic board. The chessboard is of height $H$ and width $W$. Here are some restrictions you need to know. * The knight is so straightforward and ardent that he is only willing to move towards the right and the bottom. In other words, in each step he only moves to a square with a bigger row number and a bigger column number. Note that, this might mean that there is no way to achieve his goal, for example, on a 3 by 10 board. * There are $R$ squares on the chessboard that contain rocks with evil power. Your knight may not land on any of such squares, although flying over them during a jump is allowed. Your task is to find the number of unique ways for the knight to move from the top-left corner to the bottom-right corner, under the above restrictions. It should be clear that sometimes the answer is huge. You are asked to output the remainder of the answer when divided by $10007$, a prime number.

Input begins with a line containing a single integer, $N$. $N$ test cases follow. The first line of each test case contains 3 integers, $H$, $W$, and $R$. The next $R$ lines each contain 2 integers each, $r$ and $c$, the row and column numbers of one rock. You may assume that $(1, 1)$ and $(H, W)$ never contain rocks and that no two rocks are at the same position.

For each test case, output a single line of output, prefixed by "Case #$X$: ", where $X$ is the 1-based case number, followed by a single integer indicating the number of ways of reaching the goal, modulo $10007$.

**Limits** - $1 \leq N \leq 100$ - $0 \leq R \leq 10$ **Small dataset (5 Pts, Test set 1 - Visible)** - $1 \leq W \leq 100$ - $1 \leq H \leq 100$ - $1 \leq r \leq H$ - $1 \leq c \leq W$ **Large dataset (20 Pts, Test set 2 - Hidden)** - $1 \leq W \leq 10^{8}$ - $1 \leq H \leq 10^{8}$ - $1 \leq r \leq H$ - $1 \leq c \leq W$