每个机场都有行李提取区,巴尔贝索沃机场也不例外。在某个时候,谢列梅捷沃机场的一位管理员提出了一个不寻常的想法:将行李提取传送带的传统形状从旋转木马改为更复杂的形式。
假设行李提取区域表示为大小为 $$$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$$$ 的方法数量。
示例
输入复制
52 4 21 12 22 41 4 11 11 45 5 112 53 44 55 44 35 24 13 22 11 22 31 43 4 41 22 13 22 33 43 3 22 21 11 3
输出复制
2 0 2 5 1
注意
在第一个测试用例中,有两种可能的路径:
- $$$(1,1) \到 (2,1) \到 (2, 2) \到 (2, 3) \到 (2, 4)$$$
- $$$(1,1) \到 (1,2) \到 (2, 2) \到 (2, 3) \到 (2, 4)$$$
在第二个测试用例中,没有合适的路径,因为单元格 $$$(1,1)$$$ 和 $$$(1,4)$$$ 没有公共相邻单元格。