ThreeRooks

Time limit8sMemory limit512 MB

Summary

Count the ways to place 3 rooks on a huge X by Y board with K rabbits, where a rabbit between two rooks blocks their attack.

Level: Medium7 of 10
Topics: Math, Combinatorics, Hash map, Sorting
Solved: No attempts yet

Problem

A cat is practicing chess.

The cat wants to place 3 rooks on an $X \times Y$ chessboard. $K$ rabbits are sitting on $K$ of the squares. The $i$ -th rabbit is at $(x_i, y_i)$ . The top-left square has coordinates $(0, 0)$ , and the bottom-right square has coordinates $(X-1, Y-1)$ . A rook cannot be placed on a square that has a rabbit. Also, no two rooks can be placed on the same square.

Find the number of ways to place 3 rooks so that no two rooks attack each other, modulo 1,000,000,007. Two rooks attack each other if they are in the same row or the same column and no rabbit is between them.

Input

The input is given in the following format:

$X$ $Y$ $K$

$x_1$ $y_1$

...

$x_K$ $y_K$

Output

Print the number of ways to place the rooks, modulo 1,000,000,007, on one line.

Constraints

$X$ and $Y$ are between 1 and 1,000,000,000, inclusive.
$K$ is between 1 and 100,000, inclusive.
$x_i$ is between 0 and $X-1$ , inclusive.
$y_i$ is between 0 and $Y-1$ , inclusive.
No two rabbits are on the same square.

Examples2

Example 1
Input
```
3 3 1
0 0
```
Expected output
```
4
```
Example 2
Input
```
5 8 2
2 2
4 5
```
Expected output
```
3424
```