1387. 方格游戏

小 F 和小 H 在玩游戏。今天,他们在一个 N×MN \times M 的棋盘上玩游戏。小 H 想考考小 F 的数学能力,但小 F 天生数学就不好,所以想请你帮忙。

为了加大难度,小 H 会在棋盘里面加入 PP 个矩形障碍物。每个矩形障碍物用 UUDDLLRR 来表示,即在第 UU 行到第 DD 行以及在第 LL 列到第 RR 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交,并且所有非障碍物格子之间都能够直接或者间接互达,若两个非障碍物格子有公共边,那么它们直接互达并且它们的距离为 1 。

现在每一局游戏中,小 F 在棋盘中挑选一个非障碍物格子 XX,小 H 也挑另外一个非障碍物格子 YY,这一局游戏 (X,Y)(X,Y) 的得分就是 X 到 Y 的最短路径。小 F 需要计算出所有可能的游戏中的得分和,答案模 1,000,000,0071,000,000,007

注意两局游戏中只要挑选的两个格子相同则视为同一局游戏,即 (X,Y)(X, Y) 等同于 (Y,X)(Y, X)

输入

第一行三个整数 N(1N1,000,000,000)N(1 \leq N \leq 1,000,000,000)M(1M1,000,000,000)M(1 \leq M \leq 1,000,000,000)P(0P100,000)P(0 \leq P \leq 100,000)

接下来有 PP 行,每行四个正整数,UiU_iDi(1<UiDi<N)D_i (1 < U_i \leq D_i < N)LiL_iRi(1<LiRi<M)R_i(1< L_i \leq R_i < M),表示第 ii 个矩形障碍物。

对于任意两个不同的矩形障碍物 iijj,都满足 Di+1<UjD_i+1 < U_j 或者 Dj+1<UiD_j+1 < U_i,以及 Ri+1<LjR_i+1 < L_j 或者 Rj+1<LiR_j+1 < L_i

输出

只有一行一个正整数,即所有游戏的得分和模 1,000,000,0071,000,000,007

样例

标准输入 复制文本
3 3 1
2 2 2 2
标准输出 复制文本
64

提示

距离为 1 的有 8 种。

距离为 2 的有 8 种。

距离为 3 的有 8 种。

距离为 4 的有 4 种。

总共得分为 64 。

来源

THUPC 2021 初赛

登录以提交代码。
单点时限 1 秒
内存限制 512 MB
提交 1
通过 1