Vượt qua cánh cửa, BabyOrange và hoangks7 bước vào một con đường gồm \(n\) viên đá phát sáng. Tuy nhiên, mụ phù thủy liên tục ếm bùa thay đổi "độ nguy hiểm" của con đường. Mụ thực hiện \(Q\) phép thuật. Mỗi phép thuật có thể là cộng thêm độ nguy hiểm vào một đoạn đá từ \(L\) đến \(R\), hoặc yêu cầu họ phải tính tổng độ nguy hiểm từ viên đá \(u\) đến \(v\) để tìm cách bước qua.
Lưu ý: Độ nguy hiểm của \(n\) viên đá lúc đầu đều = 0 và mụ phù thủy có thể giảm độ nguy hiểm nếu \(V\) là số âm

Input

• Dòng đầu gồm \(n\) viên đá và \(Q\) truy vấn \((n, Q \le 2 \times 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng có định dạng như sau:
• \(1\) \(L\) \(R\) \(V\): Cộng \(V\) vào đoạn \([L,R]\)
• \(2\) \(u\) \(v\): Tính tổng độ nguy hiểm đoạn \([u,v]\) (modulo \(10^9\) + 7)

Output

• Mỗi lần yêu cầu tính tổng độ nguy hiệm, đưa ra một số là đáp án yêu cầu.

Example

5 4
1 1 3 5
2 2 4
1 3 5 2
2 1 5

10
21

5 8
1 1 5 1000000000
2 2 4
1 2 3 -2000000000
2 1 5
2 2 3
1 3 5 500000005
2 1 4
2 3 5

999999986
1000000000
14
3
500000001