cho.sh

끝없는 나이트 (작은 입력)

아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

체스에는 나이트라는 기물이 있다. 나이트는 다른 기물처럼 직선으로 움직이지 않고 L자 모양으로 뛴다. 정확히 말하면 나이트는 (r1−r2)2+(c1−c2)2=5(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5가 성립할 때에만 칸 (r1,c1)(r_1, c_1)에서 칸 (r2,c2)(r_2, c_2)로 뛸 수 있다.

이 문제에서는 나이트 한 마리가 높이 HH, 너비 WW인 거대한 체스판의 왼쪽 위 칸 (1,1)(1, 1)에서 오른쪽 아래 칸 (H,W)(H, W)까지 이동한다.

제약은 두 가지다.

  • 나이트는 오른쪽과 아래쪽으로만 움직인다. 한 번 뛸 때마다 행 번호와 열 번호가 모두 더 큰 칸으로 내려앉는다. 그래서 목표 칸에 도달하는 방법이 하나도 없을 수도 있다. 3행 10열 판이 그런 예다.
  • 체스판에는 사악한 힘이 담긴 바위가 놓인 칸이 RR개 있다. 나이트는 그 칸에 내려앉을 수 없다. 다만 뛰는 도중에 그 위를 지나가는 것은 괜찮다.

이 조건에서 나이트가 왼쪽 위 칸에서 오른쪽 아래 칸까지 가는 서로 다른 방법의 수를 구한다. 답이 매우 커질 수 있으므로 소수 10007로 나눈 나머지를 출력한다.

입력

첫째 줄에 정수 NN이 주어진다. 이어서 NN개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 HH, WW, RR가 주어진다. 다음 RR개의 줄에는 바위 한 개의 행 번호 rr와 열 번호 cc가 주어진다. (1,1)(1, 1)과 (H,W)(H, W)에는 바위가 없고, 두 바위가 같은 칸에 놓이는 일도 없다.

제한

  • 1≤N≤1001 \le N \le 100
  • 0≤R≤100 \le R \le 10
  • 1≤W≤1001 \le W \le 100
  • 1≤H≤1001 \le H \le 100
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

출력

각 테스트 케이스마다 한 줄을 출력한다. 줄 앞에 Case #X: 를 붙이는데, XX는 1부터 시작하는 테스트 케이스 번호다. 그 뒤에 목표 칸에 도달하는 방법의 수를 10007로 나눈 나머지를 출력한다.