Problem:
 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

Solution (Python):
from collections import deque, Counter
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9 + 7
h, w = map(int, input().split())
n = int(input())

ans = 0

black = []
row = Counter()
column = Counter()
for _ in range(n):
    x, y = map(int, input().split())
    row[x] += 1
    column[y] += 1
    black.append((x, y))
row[h] += 1
column[w] += 1


def sqsum(x):
    return x*(x+1)*(2*x+1)//6


pre = -1
top = 0
bottom = h*w - n
area = []
for i in sorted(row.keys()):
    if i == pre+2:
        top += w
        bottom -= w
        area.append([-1, 1])
    elif i > pre+2:
        ans += (i-pre-2)*top*bottom + ((i-pre-2)*(i-pre-1)//2) * \
            w*(bottom-top) - sqsum(i-pre-2)*(w**2)
        ans %= mod
        top += (i-pre-1)*w
        bottom -= (i-pre-1)*w
        area.append([-1, i-pre-1])
    if i != h:
        top += w-row[i]
        bottom -= w-row[i]
        area.append([i])
    pre = i

R = len(area)

pre = -1
left = 0
right = h*w-n
area2 = []
for j in sorted(column.keys()):
    if j == pre+2:
        left += h
        right -= h
        area2.append([area[i][1] if area[i][0] == -1 else 1 for i in range(R)])
    elif j > pre+2:
        ans += (j-pre-2)*left*right + ((j-pre-2)*(j-pre-1)//2) * \
            h*(right-left) - sqsum(j-pre-2)*(h**2)
        ans %= mod
        left += (j-pre-1)*h
        right -= (j-pre-1)*h
        area2.append([(j-pre-1)*area[i][1] if area[i][0]
                      == -1 else (j-pre-1) for i in range(R)])
    if j != w:
        left += h-column[j]
        right -= h-column[j]
        tmp = []
        for i in range(R):
            if area[i][0] == -1:
                tmp.append(area[i][1])
            else:
                if (area[i][0], j) in black:
                    tmp.append(0)
                else:
                    tmp.append(1)
        area2.append(tmp)
    pre = j


C = len(area2)
area2 = [[area2[j][i] for j in range(C)] for i in range(R)]

vec = [[1, 0], [0, 1], [-1, 0], [0, -1]]


def bfs(p, q):
    dist = [[10**5 for _ in range(C)] for __ in range(R)]
    visited = [[False for _ in range(C)] for __ in range(R)]
    dist[p][q] = 0
    visited[p][q] = True
    q = deque([(p, q)])
    while q:
        x, y = q.popleft()
        for dx, dy in vec:
            if 0 <= x+dx < R and 0 <= y+dy < C and area2[x+dx][y+dy] != 0:
                if not visited[x+dx][y+dy]:
                    dist[x+dx][y+dy] = dist[x][y] + 1
                    visited[x+dx][y+dy] = True
                    q.append((x+dx, y+dy))
    return dist


ans2 = 0

for x in range(R*C):
    i = x//C
    j = x % C
    if area2[i][j] == 0:
        continue
    d = bfs(i, j)
    for y in range(R*C):
        k = y//C
        l = y % C
        if area2[k][l] == 0:
            continue
        ans2 += area2[i][j]*area2[k][l]*d[k][l]
        ans2 %= mod

ans2 *= pow(2, mod-2, mod)

print((ans+ans2) % mod)