题目描述

一片作业区域可以看作一个 $n$ 行 $m$ 列的网格。区域中设置了 $k$ 个投放站，第 $i$ 个投放站位于 $(a_i,b_i)$；允许多个投放站位于同一个网格位置。

从第 $0$ 秒开始，到第 $n\times m-1$ 秒结束，每一秒恰好由一个投放站向某个网格投放一枚标记。

若第 $i$ 个投放站在第 $t$ 秒选择网格 $(c_t,d_t)$，则必须同时满足：

• 在此之前，网格 $(c_t,d_t)$ 尚未被标记；

• 该网格与投放站的曼哈顿距离不超过当前时间，即

  $$|a_i-c_t|+|b_i-d_t|\le t.$$

全部投放结束后，每个网格都恰好被标记一次。记 $T_{i,j}$ 为网格 $(i,j)$ 首次被标记的时间。

请统计可能得到多少个不同的时间数组 $T$。两个数组 $S,T$ 不同，当且仅当存在一对 $(i,j)$，满足 $S_{i,j}\ne T_{i,j}$。

你需要输出方案数除以 $(nm)!$ 后，对 $2\,500\,000\,001$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 $n,m,k$；
• 接下来 $k$ 行，每行包含两个整数 $a_i,b_i$，表示第 $i$ 个投放站的位置。

输出格式

对于每组测试数据输出一行，表示所求结果对 $2\,500\,000\,001$ 取模后的值。

样例

样例输入 1

2
3 3 1
2 2
3 3 2
1 1
3 3

样例输出 1

138888889
1597222223

数据范围与提示

保证对于所有的测试点满足以下限制：$1\leq T\leq 1000,\ 1\leq n,m\leq 50000,\ 1\leq k\leq 1000,\ \sum n,\sum m\leq 10^7,\ \sum k\leq 1000$。

对于测试点 1 满足：$n\times m\leq 10,\sum(nm)\leq 20$。

对于测试点 2 $\sim$ 3 满足：$\sum(nm)\leq 10^6$。

对于测试点 4 $\sim$ 5 满足：$k=1$。

对于测试点 6 满足：$n=1$。

对于测试点 7 $\sim$ 8 满足：$\sum k\leq 100$。

对于测试点 9 $\sim$ 10 满足：无特殊限制。