Tết Trung Thu rước đèn đi chơi
Em rước đèn đi khắp phố phường
Lòng vui sướng với đèn trong tay
Em múa ca trong ánh trăng rằm
Đèn ông sao với đèn cá chép
Đèn thiên nga với đèn bướm bướm
Em rước đèn này đến cung trăng
Đèn xanh lơ với đèn tím tím
Đèn xanh lam với đèn trắng trắng
Trong ánh đèn rực rỡ muôn màu.

Hòa cùng không khí vui nhộn của ngày Tết Trung Thu, Tuân cùng các bạn trong xóm sẽ tụ họp lại và đi rước đèn ông sao từ đầu làng đến cuối làng như mọi năm.

Nhưng năm nay lạ lắm, đường làng không còn là một đường thẳng như mọi khi. Đường làng đã biến thành một bảng hình chữ nhật kích thước \(3 \times m\) và có \(n\) chướng ngại vật xuất hiện trên đường.

Mặc dù tuổi còn nhỏ nhưng não của Tuân khá to, Tuân quyết định dẫn đầu đoàn rước tìm đường vượt qua các chướng ngại vật và đi đến cuối làng. Thấy vậy là quá dễ nên Tuân còn có ý tưởng táo bạo hơn đó chính là đếm số cách đi từ đầu làng đến cuối làng sao cho Tuân và các bạn sẽ xuất phát ở ô \((2,1)\) và kết thúc ở ô \((2,m)\). Với mỗi ô \((i, j)\), Tuân chỉ có thể di chuyển đến ô:

• \((i - 1, j + 1)\) nếu \(i>1\)
• \((i, j + 1)\)
• \((i + 1, j + 1)\) nếu \(i<3\)

Có \(n\) chướng ngại vật trên đường sẽ được biểu diễn bởi bộ ba số nguyên \(a_i\), \(l_i\) và \(r_i\) và Tuân bị cấm không được di chuyển vào các ô \((a_i, j)\) với \(l_i \le j \le r_i\) (Lưu ý rằng các chướng ngại vật có thể chồng lên nhau).

Thấy số cách có vẻ rất lớn nên Tuân rất cần bạn giúp đỡ và tìm ra phần dư của nó khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(0 \leq n \leq 10 ^ 4\), \(1 \leq m \leq 10 ^ {18}\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(a_i\), \(l_i\) và \(r_i\) (\(1 \leq a_i \leq 3\), \(2 \leq l_i \leq r_i \leq m - 1\)).

Output

• In ra một số nguyên duy nhất là số cách đi thỏa mãn khi sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n = 0\) và \(m \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(m \le 10^6\).
• Subtask \(3\) (\(20\%\) số điểm): \(n = 0\).
• Subtask \(4\) (\(20\%\) số điểm): \(r_i < l_{i+1}\) với mọi \(1 \leq i \leq n - 1\).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Example

2 5  
1 3 4  
2 2 3

2