冈部喜欢散步,但知道组织的间谍可能在任何地方;这就是为什么他想知道他可以在自己的城市安全地进行多少次不同的步行。冈部的城市可以表示为所有点 (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 = ai到x = bi(含),并且位于y = ci处。保证 a1 = 0、an ≤ k ≤ bn,且 ai = bi - 1(对于 2 ≤ i ≤ n)。第 i 条线段迫使 Okabe 在 x 值满足 ai ≤ x ≤ bi 时,以 0 ≤ y ≤ ci 范围内的 y 值行走,否则他可能会被监视。这也意味着当一条线段结束而另一条线段开始时,他需要位于两条线段下方。
Okabe 现在想知道从原点到点 (k, 0) 有多少条步行满足这些条件,模 109 + 7。
输入
输入的第一行包含整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018) - 段数和目标 x 坐标。
接下来的 n 行包含三个空格分隔的整数 ai、bi 和 ci (0 ≤ ai < bi ≤ 1018, 0 ≤ ci ≤ 15) - 线段的左端和右端及其 y 坐标。
保证 a1 = 0,an ≤ k ≤ bn,并且 ai = bi - 1(对于 2 ≤ i ≤ n)。
输出
打印满足条件的行走次数,以 1000000007 (109 + 7) 为模。
示例
输入 #1
1 3 0 3 3
输出 #1
4
输入 #2
2 6 0 3 0 3 10 2
输出 #2
4
注意
上图对应于示例 1。可能的游走有:
- $$(0,0)\右箭头(1,0)\右箭头(2,0)\右箭头(3,0)$$
- $$(0,0)\右箭头(1,1)\右箭头(2,0)\右箭头(3,0)$$
- $$(0,0)\右箭头(1,0)\右箭头(2,1)\右箭头(3,0)$$
- $$(0,0)\右箭头(1,1)\右箭头(2,1)\右箭头(3,0)$$
上图对应于样本 2。Okabe 仅需步行一次即可到达 (3, 0)。此后,可能的步行是:
- $$(3,0)\右箭头(4,0)\右箭头(5,0)\右箭头(6,0)$$
- $$(3,0)\右箭头(4,0)\右箭头(5,1)\右箭头(6,0)$$
- $$(3,0)\右箭头(4,1)\右箭头(5,0)\右箭头(6,0)$$
- $$(3,0)\右箭头(4,1)\右箭头(5,1)\右箭头(6,0)$$