[JLOI/SHOI2016]方
题号:NC20151
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

输入

复制
2 2 4
1 0
1 2
0 1
2 1

输出

复制
1