问题描述

给定一个 $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$ 种。

对于每种选择，找到选定方块之间的最短距离，然后计算所有距离的和，模 $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$。
• 至少有一个白色方块。
• 对于每对白色方块 $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$

其中 dist(A, B) 是 A 和 B 之间的最短距离。这些距离的和是 $20$。

示例输入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