4055: 「JLOI / SHOI2016」方
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
上帝说，不要圆，要方，于是便有了这道题。
由于我们应该方，而且最好能够尽量方，所以上帝派我们来找正方形。上帝把我们派到了一个有 $N$ 行 $M$ 列的方格图上，图上一共有 $(N + 1) \times (M + 1)$ 个格点，我们需要做的就是找出这些格点形成了多少个正方形（换句话说，正方形的四个顶点都是格点）。
但是这个问题对于我们来说太难了，因为点数太多了，所以上帝删掉了这 $(N + 1) \times (M + 1)$ 中的 $K$ 个点。既然点变少了，问题也就变简单了，那么这个时候这些格点组成了多少个正方形呢？
输入
第一行包含三个整数 $N$，$M$，$K$，代表棋盘的行数、列数和不能选取的顶点个数。 保证 $N, M \geq 1$，$K \leq (N + 1) \times (M + 1)$。
接下来 $K$ 行，每行包含两个正整数 $X$，$Y$，代表第 $X$ 行第 $Y$ 列的格点被删掉了。保证 $0 \leq X \leq N, 0 \leq Y \leq M$，且不会出现重复的格点。约定每行的格点从上到下依次用整数 $0$ 到 $N$ 编号，每列的格点依次用 $0$ 到 $M$ 编号。
输出
输出一个正整数，代表正方形个数对 $100\,000\,007$（$10^8 + 7$）取模之后的数值。
样例输入 复制
2 2 4
1 0
1 2
0 1
2 1样例输出 复制
1提示
输入样例2
7 10 5 2 3 1 5 6 2 3 5 2 6
输出样例2
429
输入样例3
2 2 4 0 0 2 2 0 2 2 0
输出样例3
1
数据范围：| Case # | $N, M$ | $K$ | |:------:|:------:|:---:| | 1, 2 | $\leq 5$ | $\leq 25$ | | 3, 4 | $\leq 50$ | $\leq 50$ | | 5, 6 | $\leq 10^6$ | $= 0$ | | 7, 8 | $\leq 10^6$ | $\leq 50$ | | 9, 10 | $\leq 10^6$ | $\leq 200$ | | 11, 12 | $\leq 10^3$ | $\leq 2 \times 10^3$ | | 13 ~ 20 | $\leq 10^6$ | $\leq 2 \times 10^3$ |