# Binary Chess

##### Output:

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.

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$).
# Points Constraints
1 0 Examples
2 11 $R, C \le 1000$ and $N \le \min(R \cdot C,\ 1000)$
3 19 $R, C \le 1000$
4 19 $N \le \min(R \cdot C,\ 1000)$

# 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


## Problem info

ID: 1936

Editor: stefdasca

Author:

Source: IIOT 2023-24 Round I

Tags: