P7497 Quadrilateral Applause

> Read out their names, and let them return to the stage once again. Mike is going to perform a brand-new acrobatics show at the Moon River Circus!

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$.

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.

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

#### 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