Runner's Problem

题意翻译

有一个 $3 \times m$ 的田野,一开始你在 $(2, 1)$ 位置。 如果你在 $(i,j)$ 位置,在不出界的前提下,可以走到 $(i,j+1),(i\pm 1,j+1)$。 有 $n$ 段障碍,障碍不能走。每段障碍都有 $3$ 个参数 $a_i,l_i,r_i$,表示这段障碍在第 $a_i$ 行,且左右端点分别为 $l_i$ 和 $r_i$。具体地,对于所有的 $l_i \le j \le r_i$,田野的 $(a_i, j)$ 上有障碍。 询问从 $(2, 1)$ 到达 $(2, m)$ 的方案数,答案对 $10^9 + 7$ 取模。

题目描述

You are running through a rectangular field. This field can be represented as a matrix with $ 3 $ rows and $ m $ columns. $ (i,j) $ denotes a cell belonging to $ i $ -th row and $ j $ -th column. You start in $ (2,1) $ and have to end your path in $ (2,m) $ . From the cell $ (i,j) $ you may advance to: - $ (i-1,j+1) $ — only if $ i&gt;1 $ , - $ (i,j+1) $ , or - $ (i+1,j+1) $ — only if $ i&lt;3 $ . However, there are $ n $ obstacles blocking your path. $ k $ -th obstacle is denoted by three integers $ a_{k} $ , $ l_{k} $ and $ r_{k} $ , and it forbids entering any cell $ (a_{k},j) $ such that $ l_{k}<=j<=r_{k} $ . You have to calculate the number of different paths from $ (2,1) $ to $ (2,m) $ , and print it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=10^{4} $ , $ 3<=m<=10^{18} $ ) — the number of obstacles and the number of columns in the matrix, respectively. Then $ n $ lines follow, each containing three integers $ a_{k} $ , $ l_{k} $ and $ r_{k} $ ( $ 1<=a_{k}<=3 $ , $ 2<=l_{k}<=r_{k}<=m-1 $ ) denoting an obstacle blocking every cell $ (a_{k},j) $ such that $ l_{k}<=j<=r_{k} $ . Some cells may be blocked by multiple obstacles.

输出格式


Print the number of different paths from $ (2,1) $ to $ (2,m) $ , taken modulo $ 10^{9}+7 $ . If it is impossible to get from $ (2,1) $ to $ (2,m) $ , then the number of paths is $ 0 $ .

输入输出样例

输入样例 #1

2 5
1 3 4
2 2 3

输出样例 #1

2