Problem
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
In this problem, one of our knights is going to undertake a chivalrous quest of moving from the topleft corner (the (1, 1) square) to the bottomright 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 topleft corner to the bottomright 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
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.
Output
For each test case, output a single line of output, prefixed by "Case #X: ", where X is the 1based case number, followed by a single integer indicating the number of ways of reaching the goal, modulo 10007.
Limits
1 ≤ N ≤ 100
0 ≤ R ≤ 10
Small dataset
1 ≤ W ≤ 100
1 ≤ H ≤ 100
1 ≤ r ≤ H
1 ≤ c ≤ W
Large dataset
1 ≤ W ≤ 10^{8}
1 ≤ H ≤ 10^{8}
1 ≤ r ≤ H
1 ≤ c ≤ W
Sample
Input 
Output 
5

Case #1: 1

Points  Correct  Attempted 

5pt  845  879 
20pt  32  173 