# 2479. 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 (r1, c1) to (r2, c2) if and only if (r1 - r2)2 + (c1 - c2)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(1 ≤ N ≤ 100). N test cases follow.

The first line of each test case contains 3 integers, H(1 ≤ H ≤ 108), W(1 ≤ W ≤ 108), and R(0 ≤ R ≤ 10). The next R lines each contain 2 integers each, r(1 ≤ r ≤ H) and c(1 ≤ c ≤ W), 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.

### 样例

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

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


0 人解决，2 人已尝试。

0 份提交通过，共有 3 份提交。

9.9 EMB 奖励。