|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||512 MB||3||3||3||100.000%|
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.
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.
5 1 1 0 4 4 1 2 1 3 3 0 7 10 2 1 2 7 1 4 4 1 3 2
Case #1: 1 Case #2: 2 Case #3: 0 Case #4: 5 Case #5: 1