SP16639 IE4 - Endless Knight

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**. **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.

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.