ThreeRooks

時間制限 : 8 sec, メモリ制限 : 65536 KB

Problem I: ThreeRooks

ねこがチェスの練習をしている.

ねこは, $X \times Y$ のチェス盤の上にルークを 3 つ置こうとしている. このチェス盤の $K$ 個のマス目にはうさぎが座っている. $i$ 匹目のうさぎの座標は $(x[i], y[i])$ である. ただし, チェス盤の左上端のマス目の座標を $(0, 0)$, 右下端のマス目の座標を $(X-1, Y-1)$ とする。うさぎが座っている場所にはルークを置くことができない. また, 1 つのマス目に複数個のルークを置くことはできない.

どの 2 つのルークも互いに攻撃し合わないようにルークを3 つ置く方法は何通りあるか, mod 1,000,000,007 で求めよ. 2 つのルークは同じ行または同じ列にあり, 間にうさぎが座っていない場合に互いに攻撃しあうものとする.

Constraints

  • $X$, $Y$ will be between 1 and 1,000,000,000, inclusive.
  • $K$ will be between 1 and 100,000, inclusive.
  • $x_i$ will be between 0 and $X-1$, inclusive.
  • $y_i$ will be between 0 and $Y-1$, inclusive.
  • No two rabbits sit on the same cell.

Input

入力は以下の形式で与えられる:

$X$ $Y$ $K$
$x_1$ $y_1$
...
$x_K$ $y_K$

Output

ルークの配置の個数を 1,000,000,007 で割ったあまりを表す整数を 1 行に出力せよ.

Sample Input 1

3 3 1
0 0

Sample Output 1

4

Sample Input 2

5 8 2
2 2
4 5

Sample Output 2

3424

Source: ACM-ICPC Japan Alumni Group Winter Camp 2011 , Day 3, Tokyo, Japan, 2011-02-20
http://acm-icpc.aitea.net/