Description

在国际象棋游戏中，有一种棋子叫做骑士。骑士很特别——它不像其他棋子那样沿直线移动，而是以“L”形跳跃。具体来说，若 $(r_1, c_1)$ 到 $(r_2, c_2)$ 满足 $(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5$，则骑士可以从 $(r_1, c_1)$ 跳到 $(r_2, c_2)$。

在本题中，我们的骑士将踏上一次骑士之旅，从左上角 $(1, 1)$ 走到右下角 $(H, W)$ 的巨大棋盘上。棋盘的高度为 $H$，宽度为 $W$。

你需要注意以下限制：

• 骑士非常正直且热情，只愿意向右和向下移动。也就是说，每一步只能跳到行号和列号都更大的格子。注意，这意味着有些情况下无法到达目标，例如在 $3 \times 10$ 的棋盘上。
• 棋盘上有 $R$ 个格子上有带有邪恶力量的石头。骑士不能落在这些格子上，但跳跃时可以飞越这些格子。

你的任务是计算骑士从左上角走到右下角的不同方案数，满足上述所有限制。显然，答案有时会非常大。请输出方案数对 $10007$ 取模的结果，$10007$ 是一个质数。

Input Format

输入以一个整数 $N$ 开头，表示测试用例数。接下来有 $N$ 组测试数据。

每组测试数据的第一行包含三个整数 $H$、$W$ 和 $R$。接下来的 $R$ 行，每行包含两个整数 $r$ 和 $c$，表示一个有石头的格子的行号和列号。保证 $(1, 1)$ 和 $(H, W)$ 不会有石头，且没有两个石头在同一位置。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$X$: "，其中 $X$ 是测试用例编号（从 1 开始），后接一个整数，表示到达目标的方案数对 $10007$ 取模的结果。

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

Hint

数据范围

• $1 \leq N \leq 100$
• $0 \leq R \leq 10$

小数据集（5 分，测试点 1 - 可见）

• $1 \leq W \leq 100$
• $1 \leq H \leq 100$
• $1 \leq r \leq H$
• $1 \leq c \leq W$

大数据集（20 分，测试点 2 - 隐藏）

• $1 \leq W \leq 10^{8}$
• $1 \leq H \leq 10^{8}$
• $1 \leq r \leq H$
• $1 \leq c \leq W$

由 ChatGPT 4.1 翻译