[JLOI2016] 方

题目描述

上帝说,不要圆,要方,于是便有了这道题。 由于我们应该方,而且最好能够尽量方,所以上帝派我们来找正方形上帝把我们派到了一个有 $N$ 行 $M$ 列的方格图上,图上一共有 $(N+1)\times(M+1)$ 个格点,我们需要做的就是找出这些格点形成了多少个正方形(换句话说,正方形的四个顶点都是格点)。 但是这个问题对于我们来说太难了,因为点数太多了,所以上帝删掉了这 $(N+1)\times(M+1)$ 中的 $K$ 个点。既然点变少了,问题也就变简单了,那么这个时候这些格点组成了多少个正方形呢?

输入输出格式

输入格式


第一行三个整数 $N, M, K$,代表棋盘的行数、 列数和不能选取的顶点个数。保证 $N, M \ge 1$, $K \le (N + 1) \times(M + 1)$。 约定每行的格点从上到下依次用整数 $0$ 到 $N$ 编号,每列的格点依次用 $0$ 到 $M$ 编号。 接下来 $K$ 行,每行两个整数 $x,y$ 代表第 $x$ 行第 $y$ 列的格点被删掉了。 保证 $0 \le x \le N \le 10^6$,$0 \le y \le M \le 10^6$,$K \le 2000$ 且不会出现重复的格点。

输出格式


仅一行一个正整数,代表正方形个数对 $100000007 ( 10^8 + 7)$ 取模之后的值。

输入输出样例

输入样例 #1

2 2 4
1 0
1 2
0 1
2 1

输出样例 #1

1