题目描述

$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\ ×\ W\ -\ N$ 個あるため、白いマス目から $2$ つマス目を選ぶ方法は $_{(H×W-N)}C_2$ 通りあります。

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

输入格式

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

$H$ $W$ $N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_N$ $y_N$

输出格式

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

题目大意

给定一个 $w\times h$ 的网格，网格之间有 $1$ 的边权。上面有 $n\le 30$ 个位置有障碍，网格大小 $10^6$，求所有非障碍点对间的最短路之和。

2 3
1
1 1

20

2 3
1
1 2

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

提示

制約

• $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$ へ移動できる

Sample Explanation 1

マス目の色は以下のようになっています(.: 白いマス目, #: 黒いマス目)。 ... .#. ここで，以下のように白いマス目にアルファベットを振ります。 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の最短距離とします。

Sample Explanation 2

以下のように白いマス目にアルファベットを振ります。 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$ となります。