English · Original
Chinese · Translation
Formal · Original
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.   
## Input
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).
## Output
Output one integer — the number of ways to pass the track modulo 109 + 7.
[samples]
小女孩 Masha 喜欢冬季运动，今天她计划参加滑降滑雪比赛。
赛道由一个 #cf_span[n × m] 的网格组成，网格中包含若干矩形障碍物，每个障碍物由网格中的方格构成。Masha 需要从方格 #cf_span[(1, 1)] 移动到方格 #cf_span[(n, m)]。她每次只能向右或向上移动到相邻的方格。如果某个方格被障碍物占据，则不允许移动到该方格。
可以观察到，每个障碍物实际上有两种通过方式：要么障碍物位于 Masha 路径的右侧，要么位于左侧。Masha 喜欢尝试所有可能的方式，因此她想知道有多少种不同的方式可以通过赛道。两种方式被认为是不同的，当且仅当存在某个障碍物，在一种方式中它位于路径右侧，而在另一种方式中它位于路径左侧。
请帮助 Masha 计算通过赛道的方式数量。由于答案可能很大，Masha 希望知道结果对 #cf_span[109 + 7] 取模的值。
下图展示了样例测试中通过赛道的不同方式。
输入数据的第一行包含三个正整数：#cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[3 ≤ n, m ≤ 106]，#cf_span[0 ≤ k ≤ 105]）—— 分别表示赛道的尺寸和障碍物的数量。
接下来的 #cf_span[k] 行，每行包含四个正整数：#cf_span[x1]、#cf_span[y1]、#cf_span[x2]、#cf_span[y2]（#cf_span[1 ≤ x1 ≤ x2 ≤ n]，#cf_span[1 ≤ y1 ≤ y2 ≤ m]）—— 分别表示障碍物左下角和右上角方格的坐标。
保证方格 #cf_span[(1, 1)] 和 #cf_span[(n, m)] 上没有障碍物，且任意两个障碍物不重叠（但可能相接）。
输出一个整数——通过赛道的方式数量对 #cf_span[109 + 7] 取模的结果。
## Input
输入数据的第一行包含三个正整数：#cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[3 ≤ n, m ≤ 106]，#cf_span[0 ≤ k ≤ 105]）—— 分别表示赛道的尺寸和障碍物的数量。接下来的 #cf_span[k] 行，每行包含四个正整数：#cf_span[x1]、#cf_span[y1]、#cf_span[x2]、#cf_span[y2]（#cf_span[1 ≤ x1 ≤ x2 ≤ n]，#cf_span[1 ≤ y1 ≤ y2 ≤ m]）—— 分别表示障碍物左下角和右上角方格的坐标。保证方格 #cf_span[(1, 1)] 和 #cf_span[(n, m)] 上没有障碍物，且任意两个障碍物不重叠（但可能相接）。
## Output
输出一个整数——通过赛道的方式数量对 #cf_span[109 + 7] 取模的结果。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid, and $ k \in \mathbb{Z}_{\geq 0} $ the number of rectangular obstacles.
Let $ \mathcal{O} = \{O_1, \dots, O_k\} $ be the set of obstacles, where each $ O_i = [x_{i,1}, x_{i,2}] \times [y_{i,1}, y_{i,2}] $ is a axis-aligned rectangle.
Let $ P $ be the set of monotonic paths from $ (1,1) $ to $ (n,m) $ using only right $ (1,0) $ and up $ (0,1) $ moves, avoiding all obstacle cells.
**Constraints**
1. $ 3 \leq n, m \leq 10^6 $
2. $ 0 \leq k \leq 10^5 $
3. No obstacle contains $ (1,1) $ or $ (n,m) $
4. Obstacles do not overlap (may touch)
**Objective**
Count the number of paths from $ (1,1) $ to $ (n,m) $ such that for each obstacle $ O_i $, the path passes either strictly to its left or strictly to its right — and two paths are distinct if they differ in the side (left/right) taken around at least one obstacle.
Compute this count modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "D. Slalom",
"description": {
"content": "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 tra",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF720D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.\n\nThe track is represented as a grid composed of _n_ × _m_ squares. There are rectangular obstacles at the tra...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "小女孩 Masha 喜欢冬季运动，今天她计划参加滑降滑雪比赛。\n\n赛道由一个 #cf_span[n × m] 的网格组成，网格中包含若干矩形障碍物，每个障碍物由网格中的方格构成。Masha 需要从方格 #cf_span[(1, 1)] 移动到方格 #cf_span[(n, m)]。她每次只能向右或向上移动到相邻的方格。如果某个方格被障碍物占据，则不允许移动到该方格。\n\n可以观察到，每个障碍物实际上...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the grid, and $ k \\in \\mathbb{Z}_{\\geq 0} $ the number of rectangular obstacles. \nLet $ \\mathcal{O} = \\{O_1, \\dots, O_k\\} $ be the...",
"is_translate": false,
"language": "Formal"
}
]
}