I - Simple APSP Problem

Time Limit: 3 sec / Memory Limit: 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