cho.sh

Endless Knight (Small)

Count monotone right-and-down knight paths from (1,1) to (H,W) on a grid, avoiding up to 10 blocked squares, modulo 10007.

Medium6Dynamic programmingCombinatoricsNo attempts yetTime limit5sMemory limit512 MB

Problem

Chess has a piece called the knight. Instead of moving in a straight line like the other pieces, the knight jumps in an L shape. Precisely, a knight can jump 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 travels across a huge chessboard of height HH and width WW, from the top-left square (1,1)(1, 1) to the bottom-right square (H,W)(H, W).

Two restrictions apply.

  • The knight moves only right and down. Every jump lands on a square whose row number and column number are both larger than before. Because of that, the goal square is sometimes unreachable. A board with 3 rows and 10 columns is one such case.
  • RR squares of the board hold rocks with evil power. The knight may not land on any of those squares, although flying over one during a jump is allowed.

Count the distinct ways the knight can travel from the top-left square to the bottom-right square under these restrictions. The count can grow very large, so print its remainder modulo the prime 10007.

Input

The first line contains one integer NN. 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 column number of one rock. Squares (1,1)(1, 1) and (H,W)(H, W) never hold 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≤1001 \le W \le 100
  • 1≤H≤1001 \le H \le 100
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

Output

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