CF821E.Okabe and El Psy Kongroo

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.

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 \leq k \leq b_n$，且对所有 $2 \leq i \leq n$，均有 $a_i = b_i - 1$。第 $i$ 条线段要求：当 Okabe 的横坐标 $x$ 满足 $a_i \leq x \leq b_i$ 时，其纵坐标 $y$ 必须满足 $0 \leq y \leq c_i$，否则他可能被间谍发现。这也意味着：当一条线段结束而另一条线段开始时（即在 $x = b_i = a_{i+1}$ 处），Okabe 必须同时满足这两条线段所限定的 $y$ 范围。

现在，Okabe 想知道：从原点 $(0, 0)$ 出发、到达点 $(k, 0)$ 且满足上述所有约束条件的路径总数（对 $10^9 + 7$ 取模）。

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.

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100$，$1 \leq k \leq 10^{18}$）—— 分别表示线段的数量以及目标点的 $x$ 坐标。

接下来的 $n$ 行每行包含三个用空格分隔的整数 $a_i$、$b_i$ 和 $c_i$（$0 \leq a_i < b_i \leq 10^{18}$，$0 \leq c_i \leq 15$）—— 分别表示第 $i$ 条线段的左端点、右端点及其 $y$ 坐标。

保证 $a_1 = 0$，$a_n \leq k \leq b_n$，且对所有 $2 \leq i \leq n$ 有 $a_i = b_{i-1}$。

Print the number of walks satisfying the conditions, modulo 1000000007 (109 + 7).

输出满足条件的路径数量，对 $1000000007$（即 $10^9 + 7$）取模。

The graph above corresponds to sample 1. The possible walks are:

• 
• 
• 
• 

The graph above corresponds to sample 2. There is only one walk for Okabe to reach (3, 0). After this, the possible walks are:

• 
• 
• 
• 

上图对应样例 1。可能的路径有：

• 
• 
• 
• 

上图对应样例 2。Okabe 到达点 $(3,\,0)$ 的路径仅有一条。此后，可能的路径有：

• 
• 
• 
•