간단한 APSP 문제

$H \times W$ 크기의 격자가 있다. 왼쪽 위 칸의 인덱스는 $(0, 0)$이고, 오른쪽 아래 칸의 인덱스는 $(H-1, W-1)$이다.

$N$개의 칸 $(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)$은 검은색으로 칠해져 있고, 나머지 칸은 모두 흰색이다.

흰색 칸 $A$와 $B$의 최단 거리는 흰색 칸만 거쳐서 $A$에서 $B$까지 갈 때 필요한 최소 이동 횟수이다. 한 번의 이동으로 상하좌우에 인접한 칸으로 갈 수 있다.

흰색 칸은 $HW - N$개이므로, 그중 두 칸을 고르는 방법은 $C_{HW-N}^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$로 나눈 나머지를 출력하라.

• $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$이다.
• 흰색 칸은 적어도 한 개 있다.
• 임의의 흰색 칸 $A$, $B$에 대해, 흰색 칸만 거쳐서 $A$에서 $B$로 갈 수 있다.

첫 번째 예시의 격자는 다음과 같다. '.'은 흰색 칸, '!'은 검은색 칸이다.

...
.!.

흰색 칸에 다음과 같이 알파벳을 붙인다.

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$이다.

두 번째 예시에서는 다음과 같이 알파벳을 붙인다.

ABC
DE!

이때 거리의 합은 $16$이다.