Okabe thích đi bộ nhưng biết rằng gián điệp có thể ở bất cứ đâu; đó chính là lý do tại sao anh ấy muốn biết có bao nhiêu cách khác nhau mà anh ta có thể đi trong thành phố của mình một cách an toàn. Thành phố của Okabe có thể được biểu diễn bởi các điểm (\(x, y\)) sao cho \(x\) và \(y\) không âm. Okabe bắt đầu đi tại điểm gốc (điểm (\(0, 0\))) và cần đi đến điểm (\(k, 0\)). Nếu Okabe đang ở điểm (\(x, y\)), trong một bước anh ta có thể đi đến (\(x + 1, y + 1\)), (\(x + 1, y\)), hoặc (\(x + 1, y - 1\)).

Ngoài ra, có \(n\) đoạn đường ngang, đoạn thứ \(i\) từ \(x=a_i\) đến \(x=b_i\) và ở tung độ \(y=c_i\). Luôn đảm bảo rằng \(a_1=0, a_n \le k \le b_n\) và \(a_i=b_{i-1}\) với \(2 \le i \le n\). Đoạn đường thứ \(i\) buộc Okabe phải đi với giá trị \(y\) trong phạm vi \(0 \le y \le c_i\), còn giá trị \(x\) phải thoả mãn \(a_i \le  x \le  b_i\), nếu không anh ta có thể bị theo dõi. Điều này cũng có nghĩa là anh ta bắt buộc phải ở dưới hai đoạn đường khi một đoạn đường kết thúc và một đoạn khác bắt đầu.

Okabe muốn biết có bao nhiêu cách đi an toàn từ điểm đầu (\(0,0\)) tới điểm (\(k,0\)), kết quả \(\mod 10^9 + 7\).

Input

\(Input\)

• Dòng đầu chứa hai số nguyên \(n\) và \(k (1 \le  n \le  100, 1 \le  k \le  10^{18})\) là số đoạn đường ngang và tọa độ \(x\) của điểm kết thúc.
• \(N\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(a_i, b_i\) và \(c_i\) (\(0 \le  a_i < b_i \le  10^{18}, 0 \le  c_i \le  15\)) tương ứng là hoành độ đầu mút trái, hoành độ đầu mút phải, tung độ của một đoạn đường ngang.
• Dữ liệu luôn đảm bảo rằng \(a_1 = 0, a_n \le  k \le  b_n\), và \(a_i = b_i - 1\) với \(2 \le  i \le  n\).

Output

• Ghi số lượng cách đi thỏa mãn điều kiện, kết quả \(\mod 10^9 + 7\).

"