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₁=0, a_n ≤ k ≤ b_n và a_i=b_i-1 với 2 ≤ i ≤ n. Đoạn đường thứ i buộc Okabe phải đi với giá trị y trong phạm vi 0 ≤ y ≤ c_i, còn giá trị x phải thoả mãn a_i ≤ x ≤ 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ả modulo 10⁹ + 7.

Input:

Dòng đầu chứa hai số nguyên n và k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10¹⁸) 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 ≤ a_i < b_i ≤ 10¹⁸, 0 ≤ c_i ≤ 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₁ = 0, a_n ≤ k ≤ b_n, và a_i = b_i - 1  với  2 ≤ i ≤ n.

Output:

Ghi số lượng cách đi thỏa mãn điều kiện, kết quả modulo 10⁹ + 7.