Cipizz

În urma succesului internațional cu pizzeria Cipizz din Craiova, cei $3$ buni prieteni Dani, Andrei și Ștefan s-au decis să își deschidă fiecare câte o pizzerie nouă în parcul Romanescu. Parcul este reprezentant ca o matrice binară cu $N$ linii și $M$ coloane (indexate de la $1$) unde $0$ înseamnă căsuță liberă, respectiv $1$ indică prezența unui copac. Fiecare dorește să își poziționeze pizzeria într-o celulă liberă (celulă marcată cu $0$). Parcul din imagine va fi reprezentat astfel:

Mai mult, există un personaj negativ, Chilly Willy, care vrea să le saboteze pizzeriile, motiv pentru care aceștia s-au hotărât să își poziționeze pizzeriile în $3$ puncte distincte astfel încât fiecare din ei să aibă în vizor celelalte $2$ pizzerii, adică pentru oricare două pizzerii, să nu existe niciun copac pe linia dreaptă dintre acestea. De asemenea, pentru a își maximiza profitul, cei $3$ au dedus că așezarea optimă a pizzeriilor trebuie sa aibă forma unui triunghi dreptunghic isoscel cu o catetă pe o linie, una pe o coloană, cu ipotenuză pe o pseudo-diagonală paralelă cu diagonala principală și cu unghiul de $90\degree$ în colțul stânga-jos. Mai jos se pot vedea câteva exemple de astfel de amplasări valide:

Cerință

Vorba lungă sărăcia omului, Bogdănel este responsabil să se ocupe de toate aceste lucruri, iar acesta vă roagă să aflați în câte moduri putem să poziționăm cele $3$ pizzerii astfel încât să respectăm criteriile menționate (sau, în mod formal, câte triunghiuri de forma cerută cu perimetrul plin de valori de 0 există în această matrice binară).

Detalii de implementare

Va trebui să implementezi funcția

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

care primește ca parametri:

• $N$ și $M$, dimensiunile matricei;
• $x$ și $y$, vectori de dimensiune $K$ cu semnificația că există un copac în matrice la poziția $(x_i, y_i)$ pentru $0 \leq i < K$.

Funcția trebuie să returneze numărul de moduri în care se pot poziționa cele $3$ pizzerii modulo $1 \ 000 \ 000 \ 007$. Comisia va apela funcția o singură dată per test.

Restricții și precizări

• $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$ și $1 \leq y_i \leq M$, $\forall \ 0 \leq i < K$
• Pozițiile copacilor sunt distincte.

Exemplu

input

3 7 3
2 2
1 6
2 4

output

6

Explicație

Aici se pot vedea cele 6 soluții posibile:

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