Truy vấn cập nhật bậc 2 và tính tổng đoạn
Cho dãy $a_1,a_2,...,a_N$. Có $Q$ truy vấn, mỗi truy vấn thuộc một trong hai loại:
1 l r: tăng $a_l$ lên 1, tăng $a_{l+1}$ lên $2^2$, tăng $a_{l+2}$ lên $3^2$, ..., tăng $a_r$ lên $(r-l+1)^2$;2 l r: tính tổng $a_l + a_{l+1} + ... + a_r$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,Q \ (1\le N,Q \le 5\times10^4)$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (1\le a_i \le 10^5)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo mẫu trên $(1\le l \le r \le N)$.
Kết quả
- Với mỗi truy vấn loại 2, in kết quả sau khi chia lấy dư cho $10^9+7$ trên một dòng.
Ví dụ
Ví dụ 1
input
5 3
1 5 3 4 2
1 1 2
1 2 4
2 3 5
output
22
Comments