题目描述

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$.

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

提示

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$