配点 : $2000$ 点

問題文

$H \times W$ のマス目が与えられます。 左上隅のマス目を $(0, 0)$、右下隅のマス目を $(H-1, W-1)$ と表すことにします。

マス目のうち、$N$ 個のマス目 $(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)$ は黒く塗られており、残りは白く塗られています。

白いマス目 $A, B$ の間の最短距離を、$A$ から $B$ まで白いマス目のみを使用して移動するときの最短移動回数とします。 ただし、$1$ 回の移動では、上下左右の隣りあったマス目に移動できるものとします。

白いマス目は全部で $H \times W - N$ 個あるため、白いマス目から $2$ つマス目を選ぶ方法は $_{(H \times W-N)}C_2$ 通りあります。

この $_{(H \times W-N)}C_2$ 通りそれぞれについて、選んだマスの間の最短距離を求め、 それを全て足して $1,000,000,007=10^9+7$ で割った余りを求めてください。

制約

• $1 \leq H, W \leq 10^6$
• $1 \leq N \leq 30$
• $0 \leq x_i \leq H-1$
• $0 \leq y_i \leq W-1$
• $i \neq j$ ならば、$x_i \neq x_j$ または $y_i \neq y_j$
• 白いマス目が $1$ つ以上存在する
• 全ての白いマス目 $A, B$ について、白いマス目のみを使用して $A$ から $B$ へ移動できる

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_N$ $y_N$

出力

最短距離の総和を $10^9+7$ で割った余りを出力してください。

2 3
1
1 1

20

マス目の色は以下のようになっています(.: 白いマス目, #: 黒いマス目)。

...
.#.

ここで，以下のように白いマス目にアルファベットを振ります。

ABC
D#E

すると，

• dist(A, B) = $1$
• dist(A, C) = $2$
• dist(A, D) = $1$
• dist(A, E) = $3$
• dist(B, C) = $1$
• dist(B, D) = $2$
• dist(B, E) = $2$
• dist(C, D) = $3$
• dist(C, E) = $1$
• dist(D, E) = $4$

であり，これらの総和は $20$ となります。

ただし，dist(A, B) はマス目A, Bの最短距離とします。

2 3
1
1 2

16

以下のように白いマス目にアルファベットを振ります。

ABC
DE#

すると，

• dist(A, B) = $1$
• dist(A, C) = $2$
• dist(A, D) = $1$
• dist(A, E) = $2$
• dist(B, C) = $1$
• dist(B, D) = $2$
• dist(B, E) = $1$
• dist(C, D) = $3$
• dist(C, E) = $2$
• dist(D, E) = $1$

であり，これらの総和は $16$ となります。

3 3
1
1 1

64

4 4
4
0 1
1 1
2 1
2 2

268

1000000 1000000
1
0 0

333211937