Mirror IIOT 2023-2024 Round I | Binary Chess

There is a chess board of $R$ rows and $C$ columns.
There are $N$ cells that are occupied by chess pieces, and all other cells are empty.
You don't know what exact pieces occupy them, but you know that each piece is either a rook or a bishop.
You also know that no rook attacks a bishop, and no bishop attacks a rook.

Task

How many valid arrangements of pieces exist? Since this number might be too big, output it modulo $10^9 + 7$.
Two arrangements are considered different if there is at least one cell which is occupied by a different piece.

Input data

The input consists of:

• a line containing integers $R$, $C$, $N$.
• $N$ lines, the $i$-th of which consisting of integers $r_i$, $c_i$, which mean that the cell at the $r_i$-th row and $c_i$-th column is occupied.

Output data

The output must contain a single line consisting of integer $K$, the number of piece arrangements modulo $10^9 + 7$, such that no rook attacks a bishop and no bishop attacks a rook.

Constraints and clarifications

• $1 \leq R, C \leq 10^9$
• $1 \le N \le \min(R \cdot C, 200 \ 000)$
• $1 \leq r_i \leq R$, $1 \leq c_i \leq C$ for each $i = 0\ldots N-1$
• Each cell is occupied by at most one piece (in other words, either $r_i \neq r_j$ or $c_i \neq c_j$ for $i \neq j$).

Example 1

stdin

4 2 2
1 1
3 2

stdout

4

Example 2

stdin

3 3 3
2 1
3 3
1 1

stdout

2