AT_apc001_i.Simple APSP Problem

给定一个 $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$ 所需要移动的最小步数。每一步只能移动到上下左右相邻的格子。

由于白色格子共有 $H \times W - N$ 个，所以可以从中任选两个格子的方案数为 $_{(H\times W-N)}C_2$。

请对于所有 $_{(H\times 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$ 取余后的值。

约束条件

• $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$ 之间，仅通过白色格子可互相到达

样例说明 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 之间的最短距离。

样例说明 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$。

由 ChatGPT 5 翻译