题目描述

为了殖民火星，一些科学家受命清理这颗星球。他们建造了一台名为 Marsba 的清洁机器人，并将火星上一片广阔的限制区域划分为一个巨大的 $N \times N$ 正方形网格，其中分布着 $K$（$K \le 1000$）个不可通行的障碍物。这些格子按从左到右、逐行的顺序依次编号为从 $(0, 0)$ 到 $(N - 1, N - 1)$，其中 $N \le 10000$。Marsba 的起始点位于左上角的格子 $(0, 0)$。Marsba 的程序指令设定为：在每个格子，它有相等的概率停留在原格子或移动至一个相邻的格子。（两个格子若共享一条公共边，则称它们相邻。）这意味着总的概率 1 被均等地分配在“停留”和所有可用的行进路线之上。

具体而言，若 Marsba 当前所在的格子有 $d$ 个无不可通行障碍的相邻格子，则 Marsba 停留在原格子的概率以及移动到任意一个相邻格子的概率均为 $\frac{1}{d+1}$。

随后，那些科学家将这件事彻底遗忘了。

数千年后，一名年轻人在史料中意识到了清洁机器人 Marsba 的重要性。为了进一步的研究，他请你计算 Marsba 所在位置 $(x, y)$ 满足 $x + y \ge N - 1$ 的概率。

设该概率为形如 $p/q$ 的最简分数，你需要分别输出 $p$ 和 $q$，并用分数线分隔。

输入格式

第一行包含一个整数 $t$（$t \le 1000$），表示测试用例的数量。

对于每个测试用例，第一行包含两个正整数 $N$ 和 $K$。接下来的 $K$ 行，每行包含一个障碍物的坐标。

注意起始点 $(0, 0)$ 不会有障碍物，且所有测试用例保证所有无障碍格子连通。

输出格式

对于每个测试用例，首先输出其编号标头，然后以最简分数的形式输出所求的概率。

5
3 0
3 1
1 1
3 2
1 1
2 2
3 3
1 1
1 2
2 2
5 4
1 1
1 2
2 3
3 2

Case #1: 2/3
Case #2: 5/8
Case #3: 10/19
Case #4: 7/16
Case #5: 43/71

提示

翻译由 DeepSeek V3.2 完成