Binary Chess

Time limit: 1s
Memory limit: 256MB

There is a chess board of RR rows and CC columns.
There are NN 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 109+710^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 RR, CC, NN.
  • NN lines, the ii-th of which consisting of integers rir_i, cic_i, which mean that the cell at the rir_i-th row and cic_i-th column is occupied.

Output data

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

Constraints and clarifications

  • 1R,C1091 \leq R, C \leq 10^9
  • 1Nmin(RC,200 000)1 \le N \le \min(R \cdot C, 200 \ 000)
  • 1riR1 \leq r_i \leq R, 1ciC1 \leq c_i \leq C for each i=0N1i = 0\ldots N-1
  • Each cell is occupied by at most one piece (in other words, either rirjr_i \neq r_j or cicjc_i \neq c_j for iji \neq j).
# Points Constraints
1 0 Examples
2 11 R,C1000R, C \le 1000 and Nmin(RC, 1000)N \le \min(R \cdot C,\ 1000)
3 19 R,C1000R, C \le 1000
4 19 Nmin(RC, 1000)N \le \min(R \cdot C,\ 1000)
5 51 No additional constraints

Example 1


4 2 2
1 1
3 2



Example 2


3 3 3
2 1
3 3
1 1



Log in or sign up to be able to send submissions!