끝없는 나이트

체스에는 나이트라는 기물이 있다. 나이트는 특별해서, 다른 기물처럼 직선으로 이동하는 대신 "L" 모양으로 도약한다. 구체적으로, 나이트가 칸 (r1, c1)에서 (r2, c2)로 도약할 수 있는 것은 (r1 - r2)^{2} + (c1 - c2)^{2} = 5일 때, 그리고 그럴 때에만이다.

이 문제에서 나이트 하나가 거대한 보드의 왼쪽 위 모서리, 즉 (1, 1) 칸에서 오른쪽 아래 모서리, 즉 (H, W) 칸으로 이동하는 기사도적인 모험에 나선다. 체스판의 높이는 H이고 너비는 W이다.

알아야 할 몇 가지 제약은 다음과 같다.

• 나이트는 매우 올곧고 열정적이어서 오른쪽과 아래쪽으로만 이동하려 한다. 다시 말해, 각 단계에서 행 번호와 열 번호가 모두 더 큰 칸으로만 이동한다. 예를 들어 3행 10열 보드에서는 이 때문에 목표를 달성할 방법이 없을 수도 있음에 유의한다.

• 체스판에는 사악한 힘을 지닌 바위가 놓인 R개의 칸이 있다. 도약하는 동안 그 위를 날아가는 것은 허용되지만, 나이트는 그러한 칸 어디에도 착지할 수 없다.

위 제약을 따르면서 나이트가 왼쪽 위 모서리에서 오른쪽 아래 모서리로 이동하는 서로 다른 방법의 수를 구하는 것이 과제이다. 때로는 답이 매우 크다는 점은 명백하다. 답을 소수 10007로 나눈 나머지를 출력해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ N ≤ 100 0 ≤ R ≤ 10

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ W ≤ 100 1 ≤ H ≤ 100 1 ≤ r ≤ H 1 ≤ c ≤ W

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ W ≤ $10^{8}$ 1 ≤ H ≤ $10^{8}$ 1 ≤ r ≤ H 1 ≤ c ≤ W

입력은 정수 N 하나가 포함된 줄로 시작한다. 이어서 N개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 정수 3개인 H, W, R이 주어진다. 이어지는 R개의 줄에는 각각 정수 2개인 r과 c가 주어지며, 이는 바위 하나의 행 번호와 열 번호이다. (1, 1)과 (H, W)에는 바위가 절대 없으며, 어떤 두 바위도 같은 위치에 있지 않다고 가정해도 된다.

각 테스트 케이스마다 "Case #X: "가 앞에 붙은 한 줄을 출력한다. 여기서 X는 1부터 세는 케이스 번호이며, 그 뒤에는 목표에 도달하는 방법의 수를 10007로 나눈 나머지를 나타내는 정수 하나를 출력한다.