cho.sh

Endless Knight (Large)

Count right-and-down knight paths from (1,1) to (H,W) on a board up to 1e8 wide, avoiding at most 10 rocks, modulo 10007.

Medium7Dynamic programmingCombinatoricsMathImplementationNo attempts yetTime limit5sMemory limit512 MB

Problem

Chess has a piece called the knight. It does not move in a straight line like the other pieces, it jumps in an L shape. Precisely, a knight jumps from square (r1,c1)(r_1, c_1) to square (r2,c2)(r_2, c_2) if and only if (r1−r2)2+(c1−c2)2=5(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5.

In this problem one knight has to cross a gigantic board of height HH and width WW, from the top left square (1,1)(1, 1) to the bottom right square (H,W)(H, W).

The rules are these.

  • The knight only moves right and down. Every jump lands on a square whose row number and column number are both larger. Because of that, the goal is sometimes unreachable. On a 3×103 \times 10 board, for example, there is no way at all.
  • RR squares of the board hold rocks. The knight may not land on such a square, although flying over one during a jump is allowed.

Count the distinct ways for the knight to go from (1,1)(1, 1) to (H,W)(H, W). Two ways are distinct when the sequence of squares the knight lands on differs. The count gets huge, so print its remainder modulo the prime 10007.

Input

The first line contains a single integer NN, the number of test cases. NN test cases follow.

The first line of each test case contains three integers HH, WW, and RR. Each of the next RR lines contains two integers rr and cc, the row number and the column number of one rock. Neither (1,1)(1, 1) nor (H,W)(H, W) holds a rock, and no two rocks share a square.

Limits

  • 1≤N≤1001 \le N \le 100
  • 0≤R≤100 \le R \le 10
  • 1≤W≤1081 \le W \le 10^8
  • 1≤H≤1081 \le H \le 10^8
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

Output

For each test case, print one line holding Case #X: followed by the number of ways to reach the goal square, taken modulo 10007. XX is the 1 based test case number.