小女孩玛莎喜欢冬季运动,今天她打算参加回转滑雪。
轨道表示为由 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