1266: #2025. 「JLOI / SHOI2016」方

Memory Limit:256 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

上帝说,不要圆,要方,于是便有了这道题。

由于我们应该方,而且最好能够尽量方,所以上帝派我们来找正方形。上帝把我们派到了一个有 NNNMMM 列的方格图上,图上一共有 (N+1)×(M+1)(N + 1) \times (M + 1)(N+1)×(M+1) 个格点,我们需要做的就是找出这些格点形成了多少个正方形(换句话说,正方形的四个顶点都是格点)。

但是这个问题对于我们来说太难了,因为点数太多了,所以上帝删掉了这 (N+1)×(M+1)(N + 1) \times (M + 1)(N+1)×(M+1) 中的 KKK 个点。既然点变少了,问题也就变简单了,那么这个时候这些格点组成了多少个正方形呢?

输入格式

第一行包含三个整数 NNNMMMKKK,代表棋盘的行数、列数和不能选取的顶点个数。 保证 N,M≤1N, M \leq 1N,M1K≤(N+1)×(M+1)K \leq (N + 1) \times (M + 1)K(N+1)×(M+1)
接下来 KKK 行,每行包含两个正整数 XXXYYY,代表第 XXX 行第 YYY 列的格点被删掉了。保证 0≤X≤N,0≤Y≤M0 \leq X \leq N, 0 \leq Y \leq M0XN,0YM,且不会出现重复的格点。约定每行的格点从上到下依次用整数 000NNN 编号,每列的格点依次用 000MMM 编号。

输出格式

输出一个正整数,代表正方形个数对 100000007100\,000\,007100000007108+710^8 + 7108+7)取模之后的数值。

样例

样例输入 1

2 2 4
1 0
1 2
0 1
2 1

样例输出 1

1

样例解释 1

如图所示,我们删掉了其中的四个格点,那么剩下的唯一的正方形便是最大的 2×22 \times 22×2 的正方形了。

square-sample1.png

样例输入 2

7 10 5
2 3
1 5
6 2
3 5
2 6

样例输出 2

729

样例输入 3

2 2 4
0 0
2 2
0 2
2 0

样例输出 3

1

样例解释 3

还剩下一个边长为 2\sqrt 22 的正方形。

数据范围与提示

Case # N,MN, MN,M KKK
1, 2 ≤5\leq 55 ≤25\leq 2525
3, 4 ≤50\leq 5050 ≤50\leq 5050
5, 6 ≤106\leq 10^6106 =0= 0=0
7, 8 ≤106\leq 10^6106 ≤50\leq 5050
9, 10 ≤106\leq 10^6106 ≤200\leq 200200
11, 12 ≤103\leq 10^3103 ≤2×103\leq 2 \times 10^32×103
13 ~ 20 ≤106\leq 10^6106 ≤2×103\leq 2 \times 10^32×103