题目描述

城市规划师 Rika 正在分析一张巨大的方格地图。地图共有 $H$ 行 $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$。现在要在所有无序白格对中，分别计算两格之间的最短距离，并求这些距离的总和。

请输出这个总和对

$$10^9+7$$

取模后的结果。

题目保证任意两个白色格子之间都可以只经过白色格子互相到达。

输入格式

第一行包含两个整数 $H,W$。

第二行包含一个整数 $N$。

接下来 $N$ 行，每行包含两个整数 $x_i,y_i$，表示一个黑色格子的坐标。

输出格式

输出一行一个整数，表示所有无序白格对之间最短距离之和，对 $10^9+7$ 取模。

数据范围

• $1\le H,W\le 10^6$；
• $1\le N\le 10$；
• $0\le x_i\le H-1$；
• $0\le y_i\le W-1$；
• 黑色格子两两不同；
• 至少存在一个白色格子；
• 任意两个白色格子之间均连通。

样例 1

输入

2 3
1
1 1

输出

20

样例 2

输入

2 3
1
1 2

输出

16

样例 3

输入

3 3
1
1 1

输出

64

样例 4

输入

4 4
4
0 1
1 1
2 1
2 2

输出

268

样例 5

输入

1000000 1000000
1
0 0

输出

333211937

样例说明

样例 1 中，黑格记为 !，白格可标记为：

ABC
D!E

各白格对距离分别为：

$$\operatorname{dist}(A,B)=1,\operatorname{dist}(A,C)=2,\operatorname{dist}(A,D)=1,\operatorname{dist}(A,E)=3,$$$$\operatorname{dist}(B,C)=1,\operatorname{dist}(B,D)=2,\operatorname{dist}(B,E)=2,$$$$\operatorname{dist}(C,D)=3,\operatorname{dist}(C,E)=1,\operatorname{dist}(D,E)=4.$$

总和为 $20$。

样例 2 中，白格可标记为：

ABC
DE!

所有无序白格对距离之和为 $16$。