← 返回题目列表

Codeforces · 954/F

F. 跑步者的问题

中文机器翻译题面 查看原题

您正在穿过一个矩形场地。该字段可以表示为 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 表示,它禁止进入任何满足 lk ≤ j ≤ rk 的单元格 (ak, j)。

您必须计算从 (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。

示例

输入 #1

2 5
1 3 4
2 2 3

输出 #1

2