0 人解决，2 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。
单点时限: 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.
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.
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
0 人解决，2 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。