题目描述

你在 $(0,0)$。在 $(x,y)$ 时，每次移动可以到达 $(x+1,y+1),(x+1,y),(x+1,y-1)$。

平面上有 $n$ 条线段，平行于 $x$ 轴，参数为$a_i,b_i,c_i$，表示在 $(a_i,c_i)$ 到 $(b_i,c_i)$ 的一条线段，保证 $a_1 = 0$，$a_n \le k \le b_n$，$a_i=b_{i-1}$。

要求你一直在线段的下方且在 $x$ 轴上方，即 $a_i \leq x \leq b_i$ 时，$0 \leq y \leq c_i$。

问：到达 $(k,0)$ 的方案数，方案数对 $10^9+7$ 取模。

输入格式

第一行两个整数 $n,k$，$1 \le n \le 100$，$1 \le k \le 10^{18}$。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，$0 \le a_i<b_i \le 10^{18}$，$0 \le c_i \le 15$。

输出格式

一个整数，表示方案数对 $10^9+7$ 取模。

1 3
0 3 3

4

2 6
0 3 0
3 10 2

4