2479. Endless Knight

单点时限: 2.0 sec

内存限制: 256 MB

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 奖励。

创建: 15 年,9 月前.

修改: 7 年,3 月前.

最后提交: 4 年前.

来源: GCJ 2008

题目标签