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$).

# | 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)$ |

5 | 51 | No additional constraints |

## 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
```