题目描述

小 F 和小 H 在玩游戏。今天，他们在一个 $N\times M$ 的棋盘上玩游戏。小 H 想考考小 F 的数学能力，但小 F 天生数学就不好，所以想请你帮忙。为了加大难度，小 $H$ 会在棋盘里面加入 $P$ 个矩形障碍物。每个矩形障碍物用 $U$、$D$、$L$、$R$ 来表示，即在第 $U$ 行到第 $D$ 行以及在第 $L$ 列到第 $R$ 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交，并且所有非障碍物格子之间都能够直接或者间接互达，若两个非障碍物格子有公共边，那么它们直接互达并且它们的距离为 $1$。

现在每一局游戏中，小 F 在棋盘中挑选一个非障碍物格子 $X$，小 H 也挑另外一个非障碍物格子 $Y$，这一局游戏 $(X,Y)$ 的得分就是 $X$ 到 $Y$ 的最短路径。小 F 需要计算出所有可能的游戏中的得分和，答案模 $1,000,000,007$。注意两局游戏中只要挑选的两个格子相同则视为同一局游戏，即 $(X, Y)$ 等同于 $(Y,X)$。

输入格式

第一行三个整数 $N$（$1 \le N \le 1,000,000,000$），$M$（$1 \le M \le 1,000,000,000$），$P$（$0 \le P \le 100,000$）。
接下来有 $P$ 行，每行四个正整数，$U_i, D_i$（$1 < U_i \le D_i < N$），$L_i, R_i$（$1 < L_i \le R_i < M$），表示第 $i$ 个矩形障碍物。对于任意两个不同的矩形障碍物 $i$ 和 $j$，都满足 $D_i + 1 < U_j$ 或者 $D_j + 1 < U_i$，以及 $R_i + 1 < L_j$ 或者 $R_j + 1 < L_i$。

输出格式

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

样例

3 3 1
2 2 2 2

64

距离为 $1$ 的有 $8$ 种。
距离为 $2$ 的有 $8$ 种。
距离为 $3$ 的有 $8$ 种。
距离为 $4$ 的有 $4$ 种。
总共得分为 $64$。

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。