Bài toán tính độ hòa âm giữa các thành viên biểu diễn: mỗi thành viên ~i~ chơi trong khoảng thời gian từ ms ~A_i~ đến ~B_i~ (tính theo mili-giây, bao gồm cả hai đầu) với cường độ ~C_i~. Độ hòa âm của một cặp ~i,j~ (với ~i<j~) được định nghĩa là ~C_i\,C_j\,T~, trong đó ~T~ là số ms mà hai người <strong>cùng chơi. Yêu cầu tính tổng độ hòa âm của mọi cặp thành viên, kết quả lấy theo modulo ~10^9+7~.

Yêu cầu

Cho ~N~ thành viên và tổng thời lượng buổi diễn là ~M~ ms. Thành viên ~i~ chơi từ ms ~A_i~ đến ~B_i~ (đều tính cả hai đầu) với cường độ ~C_i~. Độ hòa âm của cặp ~i,j~ là ~C_i\,C_j\,T_{ij}~, trong đó ~T_{ij}~ là độ dài giao của hai đoạn ~[A_i,B_i]~ và ~[A_j,B_j]~ theo số mili-giây rời rạc. Tính tổng $$ \sum_{1\le i<j\le N} C_i\,C_j\,T_{ij} $$ theo modulo ~10^9+7~.</p>

Dữ liệu

• Dòng đầu: hai số nguyên dương ~N~, ~M~ ~(1\le N\le 10^5,\ 1\le M\le 10^6)~.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~A_i~, ~B_i~, ~C_i~ ~(1\le A_i\le B_i\le M,\ 1\le C_i\le 10^6)~.

Kết quả

• Một số nguyên là tổng độ hòa âm của tất cả các cặp thành viên sau khi chia dư ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3 5
1 3 3
2 5 2
3 4 1

Output

19

Giải thích

Tại mỗi mili-giây, xét tập đang chơi và cộng vào đáp án tổng theo công thức cặp. Cụ thể, nếu tại thời điểm ~t~ có tổng cường độ ~S_1=\sum C~ và tổng bình phương cường độ ~S_2=\sum C^2~ của những người đang chơi, thì tổng trên mọi cặp tại ~t~ là $$ \frac{S_1^2-S_2}{2}. $$ Cộng các giá trị này cho ~t=1,2,\dots,M~ sẽ thu được đáp án cuối (mỗi ms đóng góp ~1~ đơn vị thời gian).

Gợi ý (Có thể đúng hoặc sai)

• 100% số điểm cho các hướng giải có độ phức tạp ~\mathcal{O}(N+M)~ hoặc ~\mathcal{O}(N\log N)~:
  • Cách 1 (khuyến nghị, khi ~M\le 10^6~): dùng mảng hiệu trên trục thời gian rời rạc.
  • Tạo hai mảng hiệu ~D_1~, ~D_2~ kích thước ~M+2~. Với mỗi đoạn ~[A_i,B_i]~:
    • ~D_1[A_i]+=C_i~, ~D_1[B_i+1]-=C_i~
    • ~D_2[A_i]+=C_i^2~, ~D_2[B_i+1]-=C_i^2~
  • Quét ~t=1..M~, tính tiền tố ~S_1+=D_1[t]~, ~S_2+=D_2[t]~, rồi cộng vào đáp án $$ \text{ans} \mathrel{+}= \frac{S_1^2 - S_2}{2} \bmod (10^9+7). $$ Lưu ý xử lý phép chia cho ~2~ bằng nghịch đảo modular của ~2~ là ~(10^9+7+1)/2~.
  • Cách 2 (không phụ thuộc ~M~): nén toạ độ các mốc ~\{A_i, B_i+1\}~, gom thành các đoạn mà tập đang chơi không đổi. Sắp xếp sự kiện vào/ra, duy trì ~S_1~, ~S_2~; với mỗi đoạn độ dài ~len~, cộng $$ \text{ans} \mathrel{+}= len\cdot \frac{S_1^2-S_2}{2}. $$
• Tất cả phép tính thực hiện theo modulo ~10^9+7~; dùng kiểu 64-bit trước khi lấy modulo.}