題目描述

給定一個數 N 和 N 個數 A[1], ..., A[N]，需要實現 Q 次操作

• 1 L R : 詢問 ∑R i=L A[i] mod (1e9 + 7)
• 2 P V : 把 A[P] = A[P] + V, A[P + 1] = A[P + 1] + 1e9 + 7 − V

 

輸入格式

第一行一個正整數 N

第二個 N 個正整數表示序列 A

第三行一個正整數 Q

之後 Q 行每行 3 個正整數表示一次操作

輸出格式

對於每個操作 1 ，輸出一行一個正整數表示答案

Samples

3
1 10 100
3
2 2 110
1 1 2
1 3 3

121
999999997

提示

 1 ≤ N, Q ≤ 2 ∗ 105

 0 ≤ A[i] ≤ 109（對於所有滿足 1 ≤ i ≤ N 的 i）

 1 ≤ L ≤ R ≤ N 

 1 ≤ P ≤ N

 1 ≤ V ≤ 10

 

子任務

1. （25 分）N, Q ≤ 2000
2. （5 分）L = 1, R = N
3. （10 分）只有操作一
4. （60 分）没有額外的約束條件。

原始資料

• Zero1 題號：b123
• Hydro 題號：Z1123
• Locale：zh_CN
• Display：open