22586번 - 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 つのルークは同じ行または同じ列にあり, 間にうさぎが座っていない場合に互いに攻撃しあうものとする.

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

$X$ $Y$ $K$

$x_1$ $y_1$

...

$x_K$ $y_K$

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

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