P13473 [GCJ 2008 #3] Endless Knight

在国际象棋游戏中，有一种棋子叫做骑士。骑士很特别——它不像其他棋子那样沿直线移动，而是以“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$ 是一个质数。

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

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

**数据范围** - $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 翻译