小 F 和小 H 在玩游戏。今天,他们在一个 的棋盘上玩游戏。小 H 想考考小 F 的数学能力,但小 F 天生数学就不好,所以想请你帮忙。
为了加大难度,小 H 会在棋盘里面加入 个矩形障碍物。每个矩形障碍物用 、、、 来表示,即在第 行到第 行以及在第 列到第 列之间的所有格子都变成了障碍物。小 H 保证所有矩形障碍物互不相交,并且所有非障碍物格子之间都能够直接或者间接互达,若两个非障碍物格子有公共边,那么它们直接互达并且它们的距离为 1 。
现在每一局游戏中,小 F 在棋盘中挑选一个非障碍物格子 ,小 H 也挑另外一个非障碍物格子 ,这一局游戏 的得分就是 X 到 Y 的最短路径。小 F 需要计算出所有可能的游戏中的得分和,答案模 。
注意两局游戏中只要挑选的两个格子相同则视为同一局游戏,即 等同于 。
输入
第一行三个整数 ,,。
接下来有 行,每行四个正整数,,,,,表示第 个矩形障碍物。
对于任意两个不同的矩形障碍物 和 ,都满足 或者 ,以及 或者 。
输出
只有一行一个正整数,即所有游戏的得分和模 。
样例
标准输入 复制文本 |
3 3 1 2 2 2 2 |
标准输出 复制文本 |
64 |
提示
距离为 1 的有 8 种。
距离为 2 的有 8 种。
距离为 3 的有 8 种。
距离为 4 的有 4 种。
总共得分为 64 。
来源
THUPC 2021 初赛