3. Шпионы!

Филипп любит гулять по своему городу, но знает, что шпионы из ЛесТеха могут быть где угодно, поэтому он хочет узнать, по скольким различным путям он может пройти по городу Долгопрудный. Город Филиппа состоит из всех точек $(x, y)$ на плоскости таких, что $x$ и $y$ неотрицательны. Филипп должен начать прогулку в начале координат (точке $(0, 0)$) и должен закончить путь в точке $(k, 0)$. Если Филипп сейчас находится в точке $(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$, и $a_i = b_{i - 1}$ для всех $2 \leq i \leq n$. $i$-й из этих отрезков заставляет Филиппа находиться только в точках с $y$ координатой в отрезке $0 \leq y \leq c_i$, когда его $x$ координата находится в отрезке $a_i \leq x \leq b_i$. Заметьте, что когда один отрезок кончается, а другой начинается, то он должен находиться под обоими отрезками одновременно.

Филипп хочет узнать, сколько существует различных путей (последовательностей шагов) из начала координат в точку $(k, 0)$, удовлетворяющих этим ограничениям, по модулю $10^9 + 7$.

Первая строка содержит два целых числа $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 16)$ $-$ левый и правый концы отрезка, и его $y$ координата.

Гарантируется, что $a_1 = 0, a_n \leq k \leq b_n$, и $a_i = b_{i-1}$ для всех $2 \leq i \leq n$.

Выведите число путей, удовлетворяющих ограничениям, по модулю $1000000007 (10^9 + 7)$.