끝없는 나이트 (라지)

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

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

조건은 다음과 같다.

• 나이트는 오른쪽과 아래쪽으로만 움직인다. 즉 한 번 뛸 때마다 행 번호와 열 번호가 모두 커지는 칸으로 간다. 그래서 목표에 도달하는 방법이 아예 없을 수도 있다. 예를 들어 $3 \times 10$ 판에서는 방법이 하나도 없다.
• 체스판에는 바위가 놓인 칸이 $R$개 있다. 나이트는 그 칸에 착지하지 못한다. 뛰는 도중에 그 칸 위를 지나가는 것은 괜찮다.

$(1, 1)$에서 $(H, W)$까지 가는 서로 다른 방법의 수를 구하라. 나이트가 착지하는 칸의 순서가 다르면 서로 다른 방법이다. 답이 매우 커질 수 있으므로 소수 10007로 나눈 나머지를 출력한다.

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

각 테스트 케이스의 첫째 줄에 세 정수 $H$, $W$, $R$이 주어진다. 다음 $R$개의 줄에는 각각 두 정수 $r$과 $c$가 주어지며, 바위 하나가 놓인 칸의 행 번호와 열 번호를 뜻한다. $(1, 1)$과 $(H, W)$에는 바위가 없고, 두 바위가 같은 칸에 놓이지도 않는다.

제한

• $1 \le N \le 100$
• $0 \le R \le 10$
• $1 \le W \le 10^8$
• $1 \le H \le 10^8$
• $1 \le r \le H$
• $1 \le c \le W$

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