SP5522 PHU09H - Buy Your House

你正准备买房，因此联系了一家刚成立的房地产开发公司。作为他们的首位客户，公司为你提供了一项特别优惠。这家公司拥有一块宽为 $W$、高为 $H$ 的长方形土地。他们使用坐标系来测量这块土地，其中 (0, 0) 代表土地的左下角。在该系统中，距土地下边缘 $x$ 单位、距左边缘 $y$ 单位的点被表示为 $(x, y)$。 公司在这块土地上已经建了一些房子。每栋房子都是长方形，其边缘与土地的边平行。房子的位置用四个整数 $x_1, y_1, x_2, y_2$ 表示，其中 $(x_1, y_1)$ 是房子的左下角，$(x_2, y_2)$ 是右上角坐标。 这次的特殊优惠是，你可以选择一块恰好包含一栋房子的矩形区域，且该区域还可以包含任意数量的相邻空地。如果资金有限，你可以选择仅购买房子所占的区域；若预算充足，你还可以在房子周围留些空地进行美化。 不过，这些选择也有一些限制。为便于公司日后利用剩余土地，你选定的区域必须边与土地的边平行，且每个顶点的坐标都是整数。例如，可以是 (3, 2)，但不能是 (3.5, 2)。你必须确保选择的区域完整包含某一栋房子，而不能只包含一部分。你不能选择区域内有多栋房子或完全没有房子的区域。在满足这些条件的情况下，你有多少种方式购买土地？ ### 输入格式 输入的第一行是一个整数 $T$（大约 500），代表测试用例的数量。每个测试用例的第一行有两个整数 $W$ 和 $H$（$1 \leq W, H \leq 10^9$），表示土地的宽和高。接下来一行是一个整数 $N$（$1 \leq N \leq 50$），表示房子的数量。 然后，接下来的 $N$ 行，每行用四个整数 $x_1, y_1, x_2, y_2$（$0 \leq x_1 < x_2 \leq W$ 且 $0 \leq y_1 < y_2 \leq H$）描述一个房子的位置。注意，这些房子不会彼此重叠，且所有坐标均为非负整数。 ### 输出格式 对于每个测试用例，输出一行结果，格式为“Case #: W”，其中 ‘#’ 用测试用例的编号替换，‘W’ 表示你可以选择的方式总数。由于 ‘W’ 可能非常大，请输出 ‘W’ 对 1000000007 取模后的结果。 ### 示例 ``` 输入： 2 3 3 1 1 1 2 2 10 10 2 1 1 4 4 6 6 8 8 输出： Case 1: 16 Case 2: 429 ``` **本翻译由 AI 自动生成**

无

无