CF720D.Slalom

Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.

The track is represented as a grid composed of n × m squares. There are rectangular obstacles at the track, composed of grid squares. Masha must get from the square (1, 1) to the square (n, m). She can move from a square to adjacent square: either to the right, or upwards. If the square is occupied by an obstacle, it is not allowed to move to that square.

One can see that each obstacle can actually be passed in two ways: either it is to the right of Masha's path, or to the left. Masha likes to try all ways to do things, so she would like to know how many ways are there to pass the track. Two ways are considered different if there is an obstacle such that it is to the right of the path in one way, and to the left of the path in the other way.

Help Masha to find the number of ways to pass the track. The number of ways can be quite big, so Masha would like to know it modulo 109 + 7.

The pictures below show different ways to pass the track in sample tests.

小女孩玛莎喜欢冬季运动，今天她计划参加回转滑雪比赛。

赛道由一个 $n \times m$ 的方格网格表示。赛道上分布着若干矩形障碍物，每个障碍物占据若干个网格单元格。玛莎必须从方格 $(1, 1)$ 出发，到达方格 $(n, m)$。她每次只能移动到相邻的方格：向右或向上。若某方格被障碍物占据，则不允许进入该方格。

可以观察到，每个障碍物实际上有两种绕行方式：要么位于玛莎路径的右侧，要么位于其左侧。玛莎喜欢尝试所有可能的方式，因此她想知道一共有多少种不同的绕行方式。如果存在某个障碍物，在一种方式中它位于路径右侧，而在另一种方式中它位于路径左侧，则这两种方式被视为不同。

请帮助玛莎计算通过赛道的不同方式总数。由于结果可能非常大，玛莎希望得到答案对 $10^9 + 7$ 取模的结果。

下方图片展示了样例测试中通过赛道的不同方式：

The first line of input data contains three positive integers: n, m and k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — the size of the track and the number of obstacles.

The following k lines contain four positive integers each: _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1 ≤ _x_2 ≤ n, 1 ≤ _y_1 ≤ _y_2 ≤ m) — coordinates of bottom left, and top right squares of the obstacle.

It is guaranteed that there are no obstacles at squares (1, 1) and (n, m), and no obstacles overlap (but some of them may touch).

输入数据的第一行包含三个正整数：$n$、$m$ 和 $k$（$3 \leq n, m \leq 10^6$，$0 \leq k \leq 10^5$）——分别表示赛道的尺寸以及障碍物的数量。

接下来的 $k$ 行，每行包含四个正整数：$x_1$、$y_1$、$x_2$、$y_2$（$1 \leq x_1 \leq x_2 \leq n$，$1 \leq y_1 \leq y_2 \leq m$）——表示该障碍物左下角方格与右上角方格的坐标。

保证方格 $(1, 1)$ 和 $(n, m)$ 上均无障碍物，且任意两个障碍物互不重叠（但可能相邻）。

Output one integer — the number of ways to pass the track modulo 109 + 7.

输出一个整数——通过赛道的方案数对 $10^9 + 7$ 取模的结果。