您正在穿过一个矩形场地。该字段可以表示为 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