English · Original
Chinese · Translation
Formal · Original
Okabe likes to take walks but knows that spies from the Organization could be anywhere; that's why he wants to know how many different walks he can take in his city safely. Okabe's city can be represented as all points (_x_, _y_) such that _x_ and _y_ are non-negative. Okabe starts at the origin (point (0, 0)), and needs to reach the point (_k_, 0). If Okabe is currently at the point (_x_, _y_), in one step he can go to (_x_ + 1, _y_ + 1), (_x_ + 1, _y_), or (_x_ + 1, _y_ - 1).
Additionally, there are _n_ horizontal line segments, the _i_\-th of which goes from _x_ = _a__i_ to _x_ = _b__i_ inclusive, and is at _y_ = _c__i_. It is guaranteed that _a_1 = 0, _a__n_ ≤ _k_ ≤ _b__n_, and _a__i_ = _b__i_ - 1 for 2 ≤ _i_ ≤ _n_. The _i_\-th line segment forces Okabe to walk with _y_\-value in the range 0 ≤ _y_ ≤ _c__i_ when his _x_ value satisfies _a__i_ ≤ _x_ ≤ _b__i_, or else he might be spied on. This also means he is required to be under two line segments when one segment ends and another begins.
Okabe now wants to know how many walks there are from the origin to the point (_k_, 0) satisfying these conditions, modulo 109 + 7.
## Input
The first line of input contains the integers _n_ and _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 1018) — the number of segments and the destination _x_ coordinate.
The next _n_ lines contain three space-separated integers _a__i_, _b__i_, and _c__i_ (0 ≤ _a__i_ < _b__i_ ≤ 1018, 0 ≤ _c__i_ ≤ 15) — the left and right ends of a segment, and its _y_ coordinate.
It is guaranteed that _a_1 = 0, _a__n_ ≤ _k_ ≤ _b__n_, and _a__i_ = _b__i_ - 1 for 2 ≤ _i_ ≤ _n_.
## Output
Print the number of walks satisfying the conditions, modulo 1000000007 (109 + 7).
[samples]
## Note
<center></center>The graph above corresponds to sample 1. The possible walks are:
<center></center>The graph above corresponds to sample 2. There is only one walk for Okabe to reach (3, 0). After this, the possible walks are:
Okabe 喜欢散步，但他知道组织的间谍可能无处不在；因此他想知道在自己的城市中，有多少种安全的散步路径。Okabe 的城市可以表示为所有满足 $x$ 和 $y$ 非负的点 $(x, y)$。Okabe 从原点 $(0, 0)$ 出发，需要到达点 $(k, 0)$。如果 Okabe 当前位于点 $(x, y)$，那么一步之内他可以移动到 $(x + 1, y + 1)$、$(x + 1, y)$ 或 $(x + 1, y - 1)$。
此外，有 $n$ 条水平线段，第 $i$ 条线段从 $x = a_i$ 延伸到 $x = b_i$（包含端点），位于 $y = c_i$ 处。保证 $a_1 = 0$，$a_n ≤ k ≤ b_n$，且对于 $2 ≤ i ≤ n$，有 $a_i = b_{i-1}$。第 $i$ 条线段要求当 Okabe 的 $x$ 坐标满足 $a_i ≤ x ≤ b_i$ 时，其 $y$ 坐标必须在范围 $0 ≤ y ≤ c_i$ 内，否则他可能会被间谍发现。这意味着当一条线段结束而另一条开始时，他必须同时处于两条线段的约束之下。
现在 Okabe 想知道，有多少条从原点到点 $(k, 0)$ 的路径满足上述条件，结果对 $10^9 + 7$ 取模。
输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 100$，$1 ≤ k ≤ 10^{18}$）——线段数量和目标 $x$ 坐标。
接下来的 $n$ 行，每行包含三个空格分隔的整数 $a_i$、$b_i$ 和 $c_i$（$0 ≤ a_i < b_i ≤ 10^{18}$，$0 ≤ c_i ≤ 15$）——表示线段的左右端点及其 $y$ 坐标。
保证 $a_1 = 0$，$a_n ≤ k ≤ b_n$，且对于 $2 ≤ i ≤ n$，有 $a_i = b_{i-1}$。
请输出满足条件的路径数量，对 $1000000007$（$10^9 + 7$）取模。
上图对应样例 1。可能的路径有：
上图对应样例 2。Okabe 到达 $(3, 0)$ 只有一种路径。之后，可能的路径有：
## Input
输入的第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 100$，$1 ≤ k ≤ 10^{18}$）——线段数量和目标 $x$ 坐标。接下来的 $n$ 行，每行包含三个空格分隔的整数 $a_i$、$b_i$ 和 $c_i$（$0 ≤ a_i < b_i ≤ 10^{18}$，$0 ≤ c_i ≤ 15$）——表示线段的左右端点及其 $y$ 坐标。保证 $a_1 = 0$，$a_n ≤ k ≤ b_n$，且对于 $2 ≤ i ≤ n$，有 $a_i = b_{i-1}$。
## Output
请输出满足条件的路径数量，对 $1000000007$（$10^9 + 7$）取模。
[samples]
## Note
上图对应样例 1。可能的路径有：
上图对应样例 2。Okabe 到达 $(3, 0)$ 只有一种路径。之后，可能的路径有：
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of horizontal segments, $ k \in \mathbb{Z}^+ $ the target $ x $-coordinate.
Let $ S = \{(a_i, b_i, c_i) \mid i \in \{1, \dots, n\}\} $ be the set of segments, where:
- $ a_i, b_i \in \mathbb{Z} $, $ 0 \leq a_i < b_i \leq 10^{18} $,
- $ c_i \in \mathbb{Z} $, $ 0 \leq c_i \leq 15 $,
- $ a_1 = 0 $, $ a_i = b_{i-1} $ for $ 2 \leq i \leq n $, and $ a_n \leq k \leq b_n $.
Let $ \mathcal{P} $ be the set of all walks from $ (0,0) $ to $ (k,0) $, where each step moves from $ (x,y) $ to $ (x+1, y') $ with $ y' \in \{y-1, y, y+1\} $, and for all $ x \in [a_i, b_i] $, the walk satisfies $ 0 \leq y \leq c_i $.
**Constraints**
1. $ 1 \leq n \leq 100 $
2. $ 1 \leq k \leq 10^{18} $
3. $ 0 \leq c_i \leq 15 $ for all $ i $
4. The segments are contiguous: $ a_1 = 0 $, $ a_i = b_{i-1} $ for $ i = 2, \dots, n $, and $ a_n \leq k \leq b_n $
**Objective**
Compute the number of valid walks from $ (0,0) $ to $ (k,0) $ satisfying the vertical constraints imposed by the segments, modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. Okabe and El Psy Kongroo",
"description": {
"content": "Okabe likes to take walks but knows that spies from the Organization could be anywhere; that's why he wants to know how many different walks he can take in his city safely. Okabe's city can be represe",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF821E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Okabe likes to take walks but knows that spies from the Organization could be anywhere; that's why he wants to know how many different walks he can take in his city safely. Okabe's city can be represe...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Okabe 喜欢散步，但他知道组织的间谍可能无处不在；因此他想知道在自己的城市中，有多少种安全的散步路径。Okabe 的城市可以表示为所有满足 $x$ 和 $y$ 非负的点 $(x, y)$。Okabe 从原点 $(0, 0)$ 出发，需要到达点 $(k, 0)$。如果 Okabe 当前位于点 $(x, y)$，那么一步之内他可以移动到 $(x + 1, y + 1)$、$(x + 1, y)$ ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of horizontal segments, $ k \\in \\mathbb{Z}^+ $ the target $ x $-coordinate. \nLet $ S = \\{(a_i, b_i, c_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be t...",
"is_translate": false,
"language": "Formal"
}
]
}