Problem E
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\times 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 $10\, 007$, a prime number.

Input

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.

You may assume that $1 \leq N \leq 15, 0 \leq R \leq 10, 1 \leq W \leq 10^8, 1 \leq H \leq 10^8, 1 \leq r \leq H, 1 \leq c \leq W$.

Output

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 $10\, 007$.

5
1 1 0
4 4 1
2 1
3 3 0
7 10 2
1 2
7 1
4 4 1
3 2

Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 5
Case #5: 1