Okabe đi dạo

Okabe đi dạo trong thành phố, được mô hình hoá bằng tất cả các điểm $(x,y)$ với $x,y$ nguyên không âm.

Okabe xuất phát từ gốc toạ độ $(0,0)$ và muốn đến điểm $(k,0)$. Nếu đang đứng ở $(x,y)$, trong một bước anh có thể đi đến $(x+1,y+1)$, $(x+1,y)$ hoặc $(x+1,y-1)$.

Ngoài ra, có $n$ đoạn thẳng nằm ngang. Đoạn thứ $i$ trải từ $x=a_i$ đến $x=b_i$ (bao gồm hai đầu mút) và nằm ở độ cao $y=c_i$. Đoạn thứ $i$ buộc Okabe phải giữ $0\le y\le c_i$ tại mọi vị trí có hoành độ $x$ thoả mãn $a_i\le x\le b_i$.

Dữ liệu đảm bảo $a_1=0$, $a_n\le k\le b_n$ và $a_i=b_{i-1}$ với mọi $2\le i\le n$. Điều này có nghĩa là tại điểm nối giữa hai đoạn liên tiếp, Okabe phải đồng thời thoả mãn ràng buộc của cả hai đoạn.

Hãy đếm số cách đi khác nhau từ $(0,0)$ đến $(k,0)$ thoả mãn các điều kiện trên, lấy phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $c_i$.

Dữ liệu ra

Một số nguyên duy nhất: số cách đi thoả mãn, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 100$
• $1\le k\le {10}^{18}$
• $0\le a_i<b_i\le {10}^{18}$
• $0\le c_i\le 15$
• $a_1=0$, $a_n\le k\le b_n$, và $a_i=b_{i-1}$ với $2\le i\le n$

Ví dụ