Description

God said, do not be round, be square; thus this problem.

Since we should be square, and preferably as square as possible, God sent us to find squares. We are placed on a grid with $N$ rows and $M$ columns, containing $(N+1)\times(M+1)$ grid points. Our task is to count how many squares can be formed such that all four vertices are grid points.

However, the problem is too hard because there are too many points, so God deleted $K$ of these $(N+1)\times(M+1)$ points. With fewer points, the problem becomes easier. Now, how many squares can be formed from the remaining grid points?

Input Format

The first line contains three integers $N, M, K$, representing the number of rows, the number of columns, and the number of vertices that cannot be used. It is guaranteed that $N, M \ge 1$, $K \le (N+1)\times(M+1)$.

We number the rows from top to bottom by integers $0$ to $N$, and the columns from left to right by $0$ to $M$.

The next $K$ lines each contain two integers $x, y$, indicating that the grid point at row $x$, column $y$ is deleted.

It is guaranteed that $0 \le x \le N \le 10^6$, $0 \le y \le M \le 10^6$, $K \le 2000$, and no grid point is repeated.

Output Format

Output a single positive integer: the number of squares modulo $100000007$ ($10^8 + 7$).

2 2 4
1 0
1 2
0 1
2 1

1

Hint

Translated by ChatGPT 5