← 返回题目列表

Codeforces · 720/D

D. 回转

中文机器翻译题面 查看原题

小女孩玛莎喜欢冬季运动,今天她打算参加回转滑雪。

轨道表示为由 n × m 方格组成的网格。赛道上有矩形障碍物,由网格方块组成。玛莎必须从方格 (1, 1) 到达方格 (n, m)。她可以从一个方格移动到相邻的方格:向右或向上。如果该方格被障碍物占据,则不允许移动到该方格。

可以看到,每个障碍实际上可以通过两种方式通过:要么在玛莎路径的右侧,要么在左侧。玛莎喜欢尝试各种方法做事,所以她想知道有多少种方法可以通过赛道。如果存在障碍物,使得该障碍物在一种方式中位于路径的右侧,而在另一种方式中位于路径的左侧,则两种方式被认为是不同的。

帮助玛莎找到通过赛道的方法数。路数可能相当大,因此 Masha 想知道它对 109 + 7 的模。

下图展示了在示例测试中通过赛道的不同方法。

输入

输入数据的第一行包含三个正整数:n、m 和 k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — 赛道的大小和障碍物的数量。

以下 k 行每行包含四个正整数:x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) - 障碍物左下角和右上角正方形的坐标。

保证方格(1, 1)和(n, m)处没有障碍物,并且没有障碍物重叠(但有些可能会接触)。

输出

输出一个整数——通过轨道的方式数模 109 + 7。

示例

输入 #1

3 3 0

输出 #1

1

输入 #2

4 5 1
2 2 3 4

输出 #2

2

输入 #3

5 5 3
2 2 2 3
4 2 5 2
4 4 4 4

输出 #3

3