Để hỗ trợ cho đồng bào các địa phương bị ảnh hưởng của thiên tai, người ta tổ chức các hoạt động quyên góp hàng hóa. Có ~n~ điểm tập kết hàng hóa dọc theo cung đường từ Bắc vào Nam (đánh số từ ~1~ đến ~n~). Tại mỗi điểm ~i~, số lượng hàng hiện có là ~a_i~. Trước khi đưa hàng đến người dân, ban tổ chức dự kiến phân chia lại hàng giữa các điểm tập kết từ ~l~ đến ~r~:

• Gọi ~S~ là tổng lượng hàng từ điểm ~l~ đến ~r~.

• Phân chia ~S~ sao cho mỗi điểm nhận được một lượng hàng là số nguyên.

• Chênh lệch giữa điểm có nhiều hàng nhất và ít hàng nhất phải là nhỏ nhất có thể.

Ví dụ: giữa hai điểm tập kết đã nhận được số hàng ~[1, 4]~, tổng ~S = 5~. Có thể chia thành ~[2, 3]~ hoặc ~[3, 2]~ để chênh lệch là ~1~.

Yêu cầu: Hãy lập trình giải quyết các truy vấn sau:

• + ~i~ ~x~: Điểm ~i~ nhận thêm ~x~ đơn vị hàng.

• - ~l~ ~r~: Chuyển toàn bộ hàng từ ~l~ đến ~r~ cho người dân (lượng hàng tại các điểm này sau đó bằng ~0~).

• ? ~l~ ~r~: Đếm số cách phân chia hàng từ ~l~ đến ~r~ dựa trên lượng hàng hiện tại (không thực sự thay đổi giá trị).

Input

• Dòng đầu chứa ~n, q~ ~(1 \le n, q \le 2 \cdot 10^5)~.

• Dòng hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

• ~q~ dòng tiếp theo là các truy vấn dạng + ~i~ ~x~, - ~l~ ~r~ hoặc ? ~l~ ~r~.

Output

• Với mỗi truy vấn ? ~l~ ~r~, in ra số cách phân chia modulo ~1000000007~.

Scoring

Sample Input 1

3 6
1 1 2
? 2 3
? 1 3
+ 1 1
? 1 3

Sample Output 1

2
3
3

Notes

• Ban đầu, các điểm tập kết có số hàng hóa lần lượt là ~[1, 1, 2]~

• Ở truy vấn đầu tiên, chọn ra điểm tập kết thứ ~2~ và ~3~ để phân chia. Có hai cách phân chia là ~[1, 2]~ và ~[2, 1]~.

• Ở truy vấn thứ hai, ta chọn ra cả ba điểm tập kết để thử phân chia. Có ba cách phân chia là ~[1, 1, 2]~, ~[1, 2, 1]~ và ~[2, 1, 1]~

• Ở truy vấn thứ ba, điểm tập kết thứ nhất được thêm ~1~ đơn vị hàng. Số hàng lần lượt là ~[2, 1, 2]~.

• Ở truy vấn thứ tư ta lại thử chọn ra cả ba điểm tập kết. Có ba cách chia là ~[2, 2, 1]~, ~[2, 1, 2]~ và ~[1, 2, 2]~.