TREASURE

Miltos the dolphin found a treasure map and is trying his best to find the treasure. He wants you to help him decipher a sequence of ~N~ integers ~A_1, ..., A_N~, in order to find the coordinates where the treasure is located. The curious thing about this map is that it is magical, meaning each integer can change at any given moment. To help him, Miltos sends you ~Q~ commands, and you need to execute them appropriately. The commands are of two types:

• ~0\; i\; x~: Miltos informs you that the new value of the ~i~-th integer is ~x~.
• ~1\; i\; j~: Miltos asks you to display the value of ~A_i + 2A_{i+1} + 3A_{i+2} + ... + (j-i+1)A_{j}~ with ~i \le j~.

Input

The first line contains ~N~,~Q~. The next line contains the integers ~A_1~, ~...~, ~A_N~, separated by spaces. The following ~Q~ lines are of the form ~0\; i\; x~ or ~1\; i\; j~ and are Milto's commands.

Output

The output file should have as many lines as there are commands of the form ~1\; i\; j~. Each line will contain the corresponding result. You should display all results mod ~1000000007~.

Constraints

• ~1 < N,Q < 300.000~
• ~0 < A_1,\; ...\;,\; A_N,\; x < 1.000.000.000~
• ~1 \le i \le j \le N~

For 50% of the test cases ~N,Q \le 5000~

• Time limit: ~1~ sec.
• Maximum available memory: ~128~ MB.

Example of Input - Output

STDIN (treasure.in)

5 5
8 3 6 2 7
1 1 2
1 3 5
0 4 9
1 3 5
1 4 4

STDOUT (treasure.out)

14
31
45
9