Source : NOI2016贵州省选
Description
上帝说,不要圆,要方,于是便有了这道题。
由于我们应该方,而且最好能够尽量方,所以上帝派我们来找正方形。上帝把我们派到了一个有N行M列的方格图上,图上一共有 (N+1) × (M+1)
个格点,我们需要做的就是找出这些格点形成了多少个正方形(换句话说,正方形的四个顶点都是格点)。
但是这个问题对于我们来说太难了,因为点数太多了,所以上帝删掉了这(N+1) × (M+1)中的k个点。既然点变少了,问题也就变简单了,那么这个时候这些格点组成了多少个正方形呢?
Input
输入的第一行三个整数N,M,K,代表棋盘的行数、列数和不能选取的顶点个数。保证N,M≥1,K≤ (N+1) × (M+1)。
约定每行的格点从上到下依次用整数0到N编号,每列的格点依次用0到M编号。
接下来K行,每行两个整数X, Y代表第X行第Y列的格点被删掉了。
保证0≤X≤N+1,0≤Y≤M+1,且不会出现重复的格点。
Output
输出仅一行一个正整数,代表正方形个数对 100000007(108 + 7)取模之后的值。
Sample Input
2 2 4
1 0
1 2
0 1
2 1
Sample Output
1
Hint