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×103 \times 10 판에서는 방법이 하나도 없다.
  • 체스판에는 바위가 놓인 칸이 RR개 있다. 나이트는 그 칸에 착지하지 못한다. 뛰는 도중에 그 칸 위를 지나가는 것은 괜찮다.

(1,1)(1, 1)에서 (H,W)(H, W)까지 가는 서로 다른 방법의 수를 구하라. 나이트가 착지하는 칸의 순서가 다르면 서로 다른 방법이다. 답이 매우 커질 수 있으므로 소수 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≤1081 \le W \le 10^8
  • 1≤H≤1081 \le H \le 10^8
  • 1≤r≤H1 \le r \le H
  • 1≤c≤W1 \le c \le W

출력

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