English · Original
Chinese · Translation
Formal · Original
You are running through a rectangular field. This field can be represented as a matrix with 3 rows and _m_ columns. (_i_, _j_) denotes a cell belonging to _i_\-th row and _j_\-th column.
You start in (2, 1) and have to end your path in (2, _m_). From the cell (_i_, _j_) you may advance to:
* (_i_ - 1, _j_ + 1) — only if _i_ > 1,
* (_i_, _j_ + 1), or
* (_i_ + 1, _j_ + 1) — only if _i_ < 3.
However, there are _n_ obstacles blocking your path. _k_\-th obstacle is denoted by three integers _a__k_, _l__k_ and _r__k_, and it forbids entering any cell (_a__k_, _j_) such that _l__k_ ≤ _j_ ≤ _r__k_.
You have to calculate the number of different paths from (2, 1) to (2, _m_), and print it modulo 109 + 7.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 104, 3 ≤ _m_ ≤ 1018) — the number of obstacles and the number of columns in the matrix, respectively.
Then _n_ lines follow, each containing three integers _a__k_, _l__k_ and _r__k_ (1 ≤ _a__k_ ≤ 3, 2 ≤ _l__k_ ≤ _r__k_ ≤ _m_ - 1) denoting an obstacle blocking every cell (_a__k_, _j_) such that _l__k_ ≤ _j_ ≤ _r__k_. Some cells may be blocked by multiple obstacles.
## Output
Print the number of different paths from (2, 1) to (2, _m_), taken modulo 109 + 7. If it is impossible to get from (2, 1) to (2, _m_), then the number of paths is 0.
[samples]
你正在一个矩形场地上奔跑。这个场地可以表示为一个包含 #cf_span[3] 行和 #cf_span[m] 列的矩阵。#cf_span[(i, j)] 表示属于第 #cf_span[i] 行和第 #cf_span[j] 列的单元格。
你从 #cf_span[(2, 1)] 出发，必须到达 #cf_span[(2, m)]。从单元格 #cf_span[(i, j)]，你可以移动到：
然而，有 #cf_span[n] 个障碍物阻挡你的路径。第 #cf_span[k] 个障碍物由三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] 表示，它禁止进入任何满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。
你需要计算从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，并对 #cf_span[109 + 7] 取模输出。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 104], #cf_span[3 ≤ m ≤ 1018]) —— 障碍物数量和矩阵的列数。
接下来 #cf_span[n] 行，每行包含三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ ak ≤ 3], #cf_span[2 ≤ lk ≤ rk ≤ m - 1])，表示一个障碍物，它会阻挡所有满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。某些单元格可能被多个障碍物阻挡。
请输出从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，对 #cf_span[109 + 7] 取模。如果无法从 #cf_span[(2, 1)] 到达 #cf_span[(2, m)]，则路径数量为 #cf_span[0]。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 104], #cf_span[3 ≤ m ≤ 1018]) —— 障碍物数量和矩阵的列数。接下来 #cf_span[n] 行，每行包含三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ ak ≤ 3], #cf_span[2 ≤ lk ≤ rk ≤ m - 1])，表示一个障碍物，它会阻挡所有满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。某些单元格可能被多个障碍物阻挡。
## Output
请输出从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，对 #cf_span[109 + 7] 取模。如果无法从 #cf_span[(2, 1)] 到达 #cf_span[(2, m)]，则路径数量为 #cf_span[0]。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z} $, with $ 1 \leq n \leq 10^4 $, $ 3 \leq m \leq 10^{18} $.
Let $ G = ([3] \times [m], E) $ be a directed grid graph, where $ [k] = \{1, 2, \dots, k\} $, and edges exist from $ (i, j) $ to $ (i', j+1) $ if $ |i - i'| \leq 1 $, for all $ j \in [m-1] $.
Let $ O = \{(a_k, l_k, r_k) \mid k \in [n]\} $ be a set of obstacles, where each obstacle blocks all cells $ (a_k, j) $ for $ j \in [l_k, r_k] $.
Let $ S = (2, 1) $ be the start, and $ T = (2, m) $ be the target.
**Constraints**
1. $ 1 \leq n \leq 10^4 $, $ 3 \leq m \leq 10^{18} $
2. For each obstacle $ (a_k, l_k, r_k) $: $ 1 \leq a_k \leq 3 $, $ 2 \leq l_k \leq r_k \leq m-1 $
3. Cells blocked by obstacles are unreachable.
4. Paths consist of moves only from column $ j $ to $ j+1 $, and between rows differing by at most 1.
**Objective**
Compute the number of paths from $ (2,1) $ to $ (2,m) $, moving only rightward and between adjacent rows, avoiding all blocked cells, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "F. Runner's Problem",
"description": {
"content": "You are running through a rectangular field. This field can be represented as a matrix with 3 rows and _m_ columns. (_i_, _j_) denotes a cell belonging to _i_\\-th row and _j_\\-th column. You start in",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF954F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are running through a rectangular field. This field can be represented as a matrix with 3 rows and _m_ columns. (_i_, _j_) denotes a cell belonging to _i_\\-th row and _j_\\-th column.\n\nYou start in...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你正在一个矩形场地上奔跑。这个场地可以表示为一个包含 #cf_span[3] 行和 #cf_span[m] 列的矩阵。#cf_span[(i, j)] 表示属于第 #cf_span[i] 行和第 #cf_span[j] 列的单元格。\n\n你从 #cf_span[(2, 1)] 出发，必须到达 #cf_span[(2, m)]。从单元格 #cf_span[(i, j)]，你可以移动到：\n\n然而，有 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 10^4 $, $ 3 \\leq m \\leq 10^{18} $. \nLet $ G = ([3] \\times [m], E) $ be a directed grid graph, where $ [k] = \\{1, 2, \\dots, k\\} $, a...",
"is_translate": false,
"language": "Formal"
}
]
}