Cipizz

Following the international success of the Cipizz pizzeria in Craiova, the $3$ good friends Dani, Andrei and Ștefan have each decided to open a new pizzeria of their own in Romanescu Park. The park is represented as a binary matrix with $N$ rows and $M$ columns (indexed from $1$), where $0$ means a free cell, and $1$ indicates the presence of a tree. Each of them wants to place his pizzeria in a free cell (a cell marked with $0$). The park in the image will be represented as follows:

Moreover, there is a villain, Chilly Willy, who wants to sabotage their pizzerias, which is why they have decided to place their pizzerias at $3$ distinct points such that each of them has the other $2$ pizzerias in sight, meaning that for any two pizzerias, there must be no tree on the straight line between them. Also, in order to maximize their profit, the $3$ of them have deduced that the optimal placement of the pizzerias must form an isosceles right triangle with one leg on a row, one leg on a column, with the hypotenuse on a pseudo-diagonal parallel to the main diagonal, and with the $90\degree$ angle at the bottom-left corner. Below you can see a few examples of such valid placements:

Requirement

To make a long story short, Bogdănel is responsible for handling all of this, and he asks you to find out in how many ways we can place the $3$ pizzerias so that the mentioned criteria are respected (or, formally, how many triangles of the required shape, with an all-$0$ perimeter, exist in this binary matrix).

Implementation Details

You must implement the function

int count_triangles(int N, int M, std::vector<int> x, std::vector<int> y);

which receives as parameters:

• $N$ and $M$, the dimensions of the matrix;
• $x$ and $y$, vectors of size $K$, meaning that there is a tree in the matrix at position $(x_i, y_i)$ for $0 \leq i < K$.

The function must return the number of ways the $3$ pizzerias can be placed, modulo $1 \ 000 \ 000 \ 007$. The judge will call the function exactly once per test.

Constraints and Notes

• $1 \leq N, M \leq 1 \ 000 \ 000 \ 000$
• $0 \leq K \leq 5 \ 000$
• $0 \leq K \leq N \cdot M$
• $1 \leq x_i \leq N$ and $1 \leq y_i \leq M$, $\forall \ 0 \leq i < K$
• The positions of the trees are distinct.

Example

input

3 7 3
2 2
1 6
2 4

output

6

Explanation

Here are the 6 possible solutions:

0000x10  0000x10  0000010  0000010  0000010  0000010
0101xx0  0101xx0  x101000  01x1000  0101x00  01010x0
0000000  0000xxx  xx00000  00xx000  0000xx0  00000xx