在国际象棋中，有一种棋子叫做马。马的移动方式很特殊——它不像其他棋子那样沿直线移动，而是以“L”形跳跃。具体来说，马可以从格子 $(r_1, c_1)$ 跳到 $(r_2, c_2)$，当且仅当 $(r_1 - r_2)^2 + (c_1 - c_2)^2 = 5$。

在本题中，我们的马将进行一次英勇的远征，从巨型棋盘的左上角（$(1, 1)$ 格）移动到右下角（$(H, W)$ 格）。该棋盘的高度为 $H$，宽度为 $W$。

你需要了解以下限制：

• 这匹马非常直率且热忱，它只愿意向右和向下移动。换句话说，每一步它只能移动到行号更大且列号更大的格子。注意，这意味着在某些情况下（例如 $3 \times 10$ 的棋盘），可能无法到达终点。
• 棋盘上有 $R$ 个格子包含具有邪恶力量的岩石。马不能落在这些格子上，但在跳跃过程中飞越它们是被允许的。

你的任务是在上述限制条件下，计算马从左上角移动到右下角的路径总数。显然，答案有时会非常大。请输出答案对 $10007$（一个质数）取模后的结果。

输入格式

输入的第一行包含一个整数 $N$，表示测试用例的数量。

每个测试用例的第一行包含 3 个整数 $H$、$W$ 和 $R$。接下来的 $R$ 行，每行包含 2 个整数 $r$ 和 $c$，表示一块岩石的行号和列号。你可以假设 $(1, 1)$ 和 $(H, W)$ 处永远不会有岩石，且没有两块岩石位于同一位置。

输出格式

对于每个测试用例，输出一行，格式为 "Case #X: "，其中 $X$ 是从 1 开始的用例编号，后面紧跟一个整数，表示到达终点的路径数对 $10007$ 取模的结果。

数据范围

$1 \le N \le 100$

$0 \le R \le 10$

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

$1 \le W \le 100$

$1 \le H \le 100$

$1 \le r \le H$

$1 \le c \le W$

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

$1 \le W \le 10^8$

$1 \le H \le 10^8$

$1 \le r \le H$

$1 \le c \le W$

样例

输入 1

5
1 1 0
4 4 1
2 1
3 3 0
7 10 2
1 2
7 1
4 4 1
3 2

输出 1

Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 5
Case #5: 1