Вы бежите по прямоугольному полю. Поле может быть представлено, как матрица, состоящая из 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.
Выходные данные
Выведите количество различных путей из (2, 1) в (2, m) по модулю 109 + 7. Если невозможно добраться из (2, 1) в (2, m), то количество путей равно 0.