12701번 - Endless Knight (Small) 다국어

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)² + (c1 - c2)² = 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.  N test cases follow.

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

Limits

• 1 ≤ N ≤ 100
• 0 ≤ R ≤ 10
• 1 ≤ W ≤ 100
• 1 ≤ H ≤ 100
• 1 ≤ r ≤ H
• 1 ≤ c ≤ W

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.