Bạn đang quản lý một hệ thống phân phối điểm số cho các sinh viên trong một khóa học. Khóa học này có \(n\) sinh viên, ban đầu điểm số của tất cả sinh viên là \(0\). Bạn sẽ nhận được một loạt các yêu cầu cập nhật điểm số hoặc tính tổng điểm từ các giáo viên.

Mỗi yêu cầu có thể thuộc một trong hai loại sau:

• Cập nhật điểm số: Một số sinh viên từ vị trí \(l\) đến \(r\) sẽ được tăng điểm dựa trên một công thức: với mỗi sinh viên ở vị trí \(i\) \((l \le i \le r)\), điểm của họ sẽ được tăng thêm \((i-l)\times x + y\), trong đó \(x\) và \(y\) là hai giá trị được cung cấp.
• Tính tổng điểm: Giáo viên yêu cầu bạn tính tổng điểm của một nhóm sinh viên từ vị trí \(l\) đến \(r\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(n\) (số lượng sinh viên) và \(q\) (số lượng yêu cầu).
• Tiếp theo là \(q\) dòng, mỗi dòng mô tả một yêu cầu. Mỗi yêu cầu có thể thuộc một trong hai loại:
• Loại \(1\): Dòng gồm \(5\) số nguyên \(1\) \(l\) \(r\) \(x\) \(y\) (yêu cầu cập nhật điểm cho sinh viên từ \(l\) đến \(r\)).
• Loại \(2\): Dòng gồm \(3\) số nguyên \(2\) \(l\) \(r\) (yêu cầu tính tổng điểm của sinh viên từ \(l\) đến \(r\)).

Dữ liệu ra

• Đối với mỗi yêu cầu tính tổng điểm (loại \(2\)), in ra kết quả là tổng điểm của sinh viên trong khoảng từ \(l\) đến \(r\), sau đó lấy kết quả modulo \(10^9+7\)

Điều kiện

• \(1 \le n,q \le 10^5\)
• \(1 \le l,r \le n\)
• \(1 \le A_i,x \le 10^9\)

Input 1

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

Output 1

5
16

Input 2

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

Output 2

0
38
22