CF2097B Baggage Claim

每个机场都有一个行李提取区，Balbesovo 机场也不例外。某天，Sheremetyevo 机场的一位管理员提出了一个不同寻常的想法：将传统的行李传送带形状从旋转盘改为更复杂的形式。 假设行李提取区被表示为一个 $n \times m$ 的矩形网格。管理员提议传送带的路径应穿过单元格 $p_1, p_2, \ldots, p_{2k+1}$，其中 $p_i = (x_i, y_i)$。 对于每个单元格 $p_i$ 和下一个单元格 $p_{i+1}$（其中 $1 \leq i \leq 2k$），这两个单元格必须共享一条公共边。此外，路径必须是简单的，即对于任意两个不同的索引 $i \neq j$，单元格 $p_i$ 和 $p_j$ 不能重合。 不幸的是，路径计划被意外洒出的咖啡弄脏了，只保留了路径中奇数索引的单元格：$p_1, p_3, p_5, \ldots, p_{2k+1}$。你的任务是给定这些 $k+1$ 个单元格，计算恢复原始完整路径 $p_1, p_2, \ldots, p_{2k+1}$ 的可能方式的数量。 由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 3 \cdot 10^4$）。接下来是各测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 1000$，$n \cdot m \ge 3$，$1 \le k \le \left\lfloor \frac12 (n m - 1) \right\rfloor$）—— 网格的尺寸和定义路径长度的参数。 接下来是 $k+1$ 行，第 $i$ 行包含两个整数 $x_{2i-1}$ 和 $y_{2i-1}$（$1 \le x_{2i-1} \le n$，$1 \le y_{2i-1} \le m$）—— 路径上单元格 $p_{2i-1}$ 的坐标。 保证所有 $(x_{2i-1}, y_{2i-1})$ 对都是不同的。 保证所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

对于每个测试用例，输出一个整数——恢复原始完整路径的方式数量对 $10^9+7$ 取模的结果。

在第一个测试用例中，有两种可能的路径： - $(1,1) \to (2,1) \to (2, 2) \to (2, 3) \to (2, 4)$ - $(1,1) \to (1,2) \to (2, 2) \to (2, 3) \to (2, 4)$ 在第二个测试用例中，没有合适的路径，因为单元格 $(1,1)$ 和 $(1,4)$ 没有共同的相邻单元格。 翻译由 DeepSeek V3 完成