P17702 [ICPC 2019 Nanjing R] Holes

给定一个 $n \times n$ 的棋盘，行和列均从 $1$ 到 $n$ 编号。帅气少年 RDC 在指定位置打了若干个洞，其中第 $i$ 个洞位于 $(x_i, y_i)$。 RDC 还养了一只名叫 PRD 的宠物猪排骨龙。现在，PRD 喝醉了，被留在了棋盘的格子 $(r, c)$ 上。它将会随机行走，每秒以等概率移动到一个相邻的格子。这里两个格子相邻当且仅当它们共享一条公共边。当 PRD 到达一个被打洞的格子时，它会掉进洞里并开始睡觉。 现在，RDC 想知道对于每个洞，他的宠物最终停留在该洞的期望耗时。

第一行包含一个整数 $T$ ($1 \leq T \leq 20$)，表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$ 和 $k$ ($2 \leq n \leq 200, 1 \leq k \leq 200$)，表示给定棋盘的大小和洞的数量。接下来 $k$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \leq x_i, y_i \leq n$)，表示第 $i$ 个洞的位置。每组测试数据的最后一行包含两个整数 $r$ 和 $c$ ($1 \leq r, c \leq n$)，意义如上所述。 我们保证 PRD 初始时不在任何一个洞上，且所有给定的洞互不相同。我们还保证至多只有一组测试数据满足 $\max(n, k) > 5$。

对于每组测试数据，在一行内按顺序输出到达每个洞的期望耗时（以秒计）。 更确切地说，如果一个洞是可达的，且期望耗时的既约分数为 $\frac{p}{q}$，你应当输出最小的非负整数 $r$ 使得 $q \cdot r \equiv p \pmod{10^9+7}$。你可以放心地假设在所有测试数据中这样的 $r$ 总是存在。如果一个洞是不可达的，则在对应的位置输出 `GG`。

翻译由 DeepSeek V4 Pro 完成