F. Задача о бегуне
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы бежите по прямоугольному полю. Поле может быть представлено, как матрица, состоящая из 3 строк и m столбцов. (i, j) обозначает ячейку в i-й строке в j-м столбце.

Вы начинаете в (2, 1) и хотите закончить путь в (2, m). Из ячейки (i, j) можно переходить в ячейки:

  • (i - 1, j + 1) — только при i > 1,
  • (i, j + 1), или
  • (i + 1, j + 1) — только при i < 3.

Однако, на вашем пути есть n препятствий. k-е препятствие определяется тремя целыми числами ak, lk и rk, и запрещает посещать ячейки (ak, j) такие, что lk ≤ j ≤ rk.

Посчитайте количество различных путей из (2, 1) в (2, m) и выведите его по модулю 109 + 7.

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 104, 3 ≤ m ≤ 1018) — количество препятствий и количество столбцов в матрице соответственно.

Затем идут n строк, в каждой записано по три целых числа ak, lk и rk (1 ≤ ak ≤ 3, 2 ≤ lk ≤ rk ≤ m - 1), определяющие препятствие, блокирующее ячейки (ak, j) такие, что lk ≤ j ≤ rk. Некоторые клетки могут быть заблокированы несколькими препятствиями.

Выходные данные

Выведите количество различных путей из (2, 1) в (2, m) по модулю 109 + 7. Если невозможно добраться из (2, 1) в (2, m), то количество путей равно 0.

Пример
Входные данные
2 5
1 3 4
2 2 3
Выходные данные
2