Cho một dãy số nguyên có các phần tử \(a_1, a_2,..., a_n\). Hàm \(f(i,j)\) với \(1 \le i \le j \le n\) được định nghĩa như sau:

\[~f(i,j) = \sum\limits_{u = i}^{j}\sum\limits_{v = u}^{j}\sum\limits_{t = u}^{v}a_{t}~\] Ví dụ: Với dãy số 1, 4, 3, 2, ta có:

• \(f(1,4) = 1 + 4 + 3 + 2 + (1 + 4) + (4 + 3) + (3 + 2) + (1 + 4 + 3) + (4 + 3 + 2) + (1 + 4 + 3 + 2) = 54\)
• \(f(2,3) = 4 + 3 + (4+3) = 14\)

Yêu cầu: Cho dãy số \(A\) gồm \(n\) phần tử và \(n\) truy vấn, mỗi truy vấn có dạng như sau:

• C i v: Thêm phần tử giá trị \(v\) vào vị trí \(i\) với \(1 \le i \le n\)
• R i j: Tính \(f(i,j)\), với \(1 \le i \le j \le n\), kết quả chia dư \(10^9+7\)
• U i v: Thay phần tử giá trị \(v\) vào vị trí \(i\) với \(1 \le i \le n\)
• D i: Xóa phần tử ở vị trí \(i\) với \(1 \le i \le n\)

Đầu vào

Dòng đầu là một số nguyên dương \(n\)

Dòng tiếp theo gồm \(n\) số nguyên \(a_i\)

Trong \(n\) dòng cuối cùng, mỗi dòng chứa một truy vấn CRUD

Đầu ra

Với mỗi truy vấn dạng \(R\), in ra kết quả truy vấn chia dư cho \(10^9+7\)

Giới hạn

Tất cả các test, \(-0 \le a_i \le 10^9\), trong đó:

20%: \(n \le 1000\), đa dạng truy vấn

20%: \(n \le 10^5\), có truy vấn R và truy vấn U, trong đó truy vấn R luôn là R 1 n

20%: \(n \le 10^5\), có các truy vấn CUD và chỉ có 1 truy vấn R 1 n ở cuối cùng

20%: \(n \le 10^5\), có các truy vấn RUD

20%: \(n \le 10^5\), có đa dạng các loại truy vấn

Ví dụ

Đầu vào

4
1 8 2 7
C 2 4
U 3 3
D 5
R 1 4

Đầu ra

54

Giải thích

Sau truy vấn 1, dãy số trở thành: 1 4 8 2 7
Sau truy vấn 2, dãy số trở thành: 1 4 3 2 7
Sau truy vấn 3, dãy số trở thành: 1 4 3 2
Truy vấn thứ 4, in ra kết quả f(1,4) = 54 (đã tính ở trên đề bài)