/ 
実行時間制限: 3 sec / メモリ制限: 256 MB
配点 : 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 × W - N 個あるため、白いマス目から 2 つマス目を選ぶ方法は _{(H×W-N)}C_2 通りあります。
この _{(H×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 で割った余りを出力してください。
入力例 1
2 3 1 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
2 3 1 1 2
出力例 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 3 1 1 1
出力例 3
64
入力例 4
4 4 4 0 1 1 1 2 1 2 2
出力例 4
268
入力例 5
1000000 1000000 1 0 0
出力例 5
333211937
Score : 2000 points
Problem Statement
You are given an H \times W grid. The square at the top-left corner will be represented by (0, 0), and the square at the bottom-right corner will be represented by (H-1, W-1).
Of those squares, N squares (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) are painted black, and the other squares are painted white.
Let the shortest distance between white squares A and B be the minimum number of moves required to reach B from A visiting only white squares, where one can travel to an adjacent square sharing a side (up, down, left or right) in one move.
Since there are H × W - N white squares in total, there are _{(H×W-N)}C_2 ways to choose two of the white squares.
For each of these _{(H×W-N)}C_2 ways, find the shortest distance between the chosen squares, then find the sum of all those distances, modulo 1 000 000 007=10^9+7.
Constraints
- 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
- If i \neq j, then either x_i \neq x_j or y_i \neq y_j.
- There is at least one white square.
- For every pair of white squares A and B, it is possible to reach B from A visiting only white squares.
Input
Input is given from Standard Input in the following format:
H W N x_1 y_1 x_2 y_2 : x_N y_N
Output
Print the sum of the shortest distances, modulo 10^9+7.
Sample Input 1
2 3 1 1 1
Sample Output 1
20
We have the following grid (.: a white square, #: a black square).
... .#.
Let us assign a letter to each white square as follows:
ABC D#E
Then, we have:
- 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
where dist(A, B) is the shortest distance between A and B. The sum of these distances is 20.
Sample Input 2
2 3 1 1 2
Sample Output 2
16
Let us assign a letter to each white square as follows:
ABC DE#
Then, we have:
- 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
The sum of these distances is 16.
Sample Input 3
3 3 1 1 1
Sample Output 3
64
Sample Input 4
4 4 4 0 1 1 1 2 1 2 2
Sample Output 4
268
Sample Input 5
1000000 1000000 1 0 0
Sample Output 5
333211937