Вы бежите по прямоугольному полю. Поле может быть представлено, как матрица, состоящая из 3 строк и m столбцов. (i, j) обозначает ячейку в i-й строке в j-м столбце.
Вы начинаете в (2, 1) и хотите закончить путь в (2, m). Из ячейки (i, j) можно переходить в ячейки:
Однако, на вашем пути есть 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
Название |
---|