Trong trò chơi cờ vua, có một quân cờ được gọi là quân mã. Quân mã rất đặc biệt — thay vì di chuyển theo đường thẳng như các quân cờ khác, nó nhảy theo hình chữ "L". Cụ thể, một quân mã có thể nhảy từ ô \((r1, c1)\) đến ô \((r2, c2)\) khi và chỉ khi \((r1 - r2)^2 + (c1 - c2)^2 = 5\).

Trong bài toán này, một quân mã của chúng ta sẽ thực hiện một nhiệm vụ hiệp sĩ là di chuyển từ góc trên bên trái (ô \((1, 1)\)) đến góc dưới bên phải (ô \((H, W)\)) trên một bàn cờ khổng lồ. Bàn cờ có chiều cao \(H\) và chiều rộng \(W\).

Dưới đây là một số hạn chế bạn cần biết:

• Quân mã rất thẳng thắn và nhiệt huyết nên nó chỉ sẵn sàng di chuyển về phía bên phải và phía dưới. Nói cách khác, trong mỗi bước đi, nó chỉ di chuyển đến một ô có số hàng lớn hơn và số cột lớn hơn. Lưu ý rằng, điều này có nghĩa là có thể không có cách nào để đạt được mục tiêu, ví dụ như trên bàn cờ kích thước \(3 \times 10\).
• Có \(R\) ô trên bàn cờ chứa những tảng đá mang sức mạnh hắc ám. Quân mã của bạn không được phép dừng chân trên bất kỳ ô nào như vậy, mặc dù việc bay qua chúng trong khi nhảy là được phép.

Nhiệm vụ của bạn là tìm số cách duy nhất để quân mã di chuyển từ góc trên bên trái đến góc dưới bên phải, dưới các hạn chế trên. Rõ ràng là đôi khi đáp án sẽ rất lớn. Bạn được yêu cầu đưa ra phần dư của đáp án khi chia cho \(10007\), một số nguyên tố.

Dữ liệu vào

Dữ liệu vào bắt đầu bằng một dòng chứa một số nguyên duy nhất, \(N\). \(N\) bộ dữ liệu kiểm tra theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa 3 số nguyên, \(H\), \(W\), và \(R\). \(R\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên, \(r\) và \(c\), là số hàng và số cột của một tảng đá. Bạn có thể giả định rằng \((1, 1)\) và \((H, W)\) không bao giờ chứa đá và không có hai tảng đá nào ở cùng một vị trí.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất một dòng duy nhất, bắt đầu bằng "Case #X: ", trong đó X là số thứ tự bộ dữ liệu (bắt đầu từ 1), tiếp theo là một số nguyên duy nhất cho biết số cách để đạt được mục tiêu, modulo \(10007\).

Ràng buộc

• \(1 \le N \le 100\)
• \(0 \le R \le 10\)

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible):
• \(1 \le W \le 100\)
• \(1 \le H \le 100\)
• \(1 \le r \le H\)
• \(1 \le c \le W\)
• Tập dữ liệu lớn (Test set 2 - Hidden):
• \(1 \le W \le 10^8\)
• \(1 \le H \le 10^8\)
• \(1 \le r \le H\)
• \(1 \le c \le W\)

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

Nguồn

Google Code Jam 2008, Vòng 3, bài Endless Knight.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.