Description

Mike has a total of $n$ new acts, and the thrill value of the $i$-th act is $a_i$.

Next, Mike can apply several operations to modify the thrill values:

• Mike uses an ice ball: for all $l\leq i\leq r$, the thrill value of the $i$-th act increases by $x$.

• Mike uses an earth ball: for all $l\leq i\leq r$, the thrill value of the $i$-th act is multiplied by $x$.

• Mike uses a fire ball: for all $l\leq i\leq r$, the thrill value of the $i$-th act will not be affected by ice balls and earth balls in the next $x$ operations. The fire ball effect will not be overwritten.

Of course, the audience is also curious about the thrill values of each act, so during the operations you need to help Mike answer: for all $l\leq i\leq r$, what is the sum of the thrill values of the $i$-th acts. The audience also does not want the thrill values to become too large, so you need to take the result modulo $10^9+7$.

Brief statement:

You are given an array $a$ of length $n$. You need to support the following operations:

1. l r x: for all $l\leq i\leq r$, increase $a_i$ by $x$.
2. l r x: for all $l\leq i\leq r$, multiply $a_i$ by $x$.
3. l r x: for all $l\leq i\leq r$, during the next $x$ operations, $a_i$ will be locked and will not be affected by operation 1 and operation 2 (let this operation be the $k$-th operation, then in the $k+1,k+2,\cdots,k+x$-th operations, all operation 1 and operation 2 will have no effect on the interval $\left[l,r\right]$). Existing lock effects will not be overwritten (that is, suppose in the 3rd operation there is an operation 3 that locks some position for 5 operations, and in the 5th operation it locks the same position for 2 operations, then in fact this position will be locked from the 4th operation through the 8th operation). (Intuitively, a later shorter lock will not cancel an earlier longer lock.)
4. l r: query $\sum\limits_{l\leq i\leq r}a_i$, modulo $10^9+7$.

Input Format

The first line contains two positive integers $n,m$, representing the array length and the number of operations.

The second line contains $n$ integers $a_i$, representing the array $a$.

The next $m$ lines each contain three integers $opt,l,r$, representing the operation type and the range $l,r$. If $opt\leq 3$, there is also an integer $x$, representing the value $x$ for this operation.

Output Format

For every operation 4, output one integer per line, representing the result modulo $10^9+7$.

5 5
1 5 4 3 6
1 2 4 3
3 1 2 2
4 2 5
2 2 3 4
4 1 3

27
37

10 12
4 2 1 5 10 3 2 4 6 7
2 3 7 4
1 2 9 5
3 2 4 5
3 4 7 2
4 3 9
1 1 8 2
2 4 5 2
3 6 8 2
4 2 3
1 2 10 6
2 7 9 3
4 1 10

129
16
314

Hint

Explanation for Sample 1

Initially, the array is $\{1,5,4,3,6\}$.

• Perform the 1st operation, and the array becomes $\{1,8,7,6,6\}$.
• Perform the 2nd operation, and the array remains unchanged.
• Perform the 3rd operation, and the query result is $27$.
• Perform the 4th operation: since $a_2$ was locked in the 2nd operation and has not been unlocked yet, this operation only affects $a_3$, and the array becomes $\{1,8,28,6,6\}$.
• Perform the 5th operation, and the query result is $37$.

Constraints

This problem uses bundled testdata.

• Subtask 1 ( $25\%$ ): $n,m\leq2\times10^3$.
• Subtask 2 ( $8\%$ ): no operation 3.
• Subtask 3 ( $17\%$ ): for all operation 4, it is guaranteed that $l=r$.
• Subtask 4 ( $50\%$ ): no special restrictions.

For all testdata, $1\leq n,m\leq 2\times 10^5,0\leq a_i<10^9+7,1\leq l\leq r\leq n$. For all operation 1 and operation 2, it is guaranteed that $0\leq x<10^9+7$. For all operation 3, let it be the $k$-th operation, and it is guaranteed that $0\leq x\leq m-k$.

Translated by ChatGPT 5