轰炸

题目信息

时间限制: 1s

空间限制: 512M

输入文件: cannon.in

输出文件: cannon.in

题目描述

有一个 $n$ 行 $m$ 列的网格，格点坐标为 $(1,1)$ 到 $(n,m)$。有 $K$ 门大炮，每一门大炮在网格内有一个瞄准基点。在时刻 $t$，一门大炮的轰炸范围是与它的瞄准基点的曼哈顿距离不超过 $t$ 的格点。

注：点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的曼哈顿距离为 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert$

从时刻 $0$ 到 $nm-1$，这总共 $nm$ 个时刻中，每个时刻需要轰炸一个之前没有被轰炸过的格点。被轰炸的这个格点必须至少在一门大炮这个时刻的轰炸范围中。

这样，时刻 $nm-1$ 结束之后，每个格点恰好被轰炸过一次。你需要求出不同的轰炸方案数有多少种，对 $2500000001$ 取模（$2.5\times 10^9+1$，这是个质数，但是超过了有符号 int 类型的最大范围）。

两种轰炸方案不同当且仅当有一个格点在两种方案中被轰炸的时刻不同。每个时刻选择哪门大炮开火对方案是否相同没有影响。

可以证明从 $0$ 到 $nm-1$ 的每个时刻总是至少有一个从未被轰炸过的格点在至少一门大炮这个时刻的轰炸范围内。

输入格式

输入文件名为 cannon.in。

第一行，一个正整数 $T$，表示数据组数。

接下来，对于每组数据：

• 第一行，三个正整数 $n,m,K$ 表示网格行数、列数和大炮数量。
• 接下来 $K$ 行，其中第 $i$ 行两个正整数 $x_i,y_i$ 表示第 $i$ 门大炮的瞄准基点位置为 $(x_i, y_i)$。保证瞄准基点位置两两不同。

输出格式

输出文件名为 cannon.out。

输出 $T$ 行，第 $i$ 行一个非负整数表示第 $i$ 组数据的答案，对 $2500000001$ 取模。

样例

输入样例 1

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

输出样例 1

1250000001
1
1250000001
1386363637
2306547620

数据范围与提示

对于所有数据，$1\le T\le 1000, 1\le K\le \min(nm,1000), 1\le n,m \le 50000, \sum n\le 10^7, \sum m\le 10^7, \sum K\le 2000$，保证 $1\le x\le n, 1\le y\le m$。