P. In Another World With My Range Query Problems
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Touya Mochizuki was struck by a bolt of lightning. Fortunately, instead of dying, he is sent to another world with his smartphone. Unfortunately, even in this generic new fantasy world, Touya is still unable to escape from generic range query problems!

Touya has an array $$$a$$$ of length of $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$). He is now tasked with $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$) queries of two possible types. Queries of type $$$2$$$ will add a value $$$v$$$ to every $$$a_i$$$ for $$$l \le i \le r$$$. Queries of type $$$1$$$ will ask him what is the sum of all subarrays in the range $$$l \dots r$$$, that is to say, $$$\displaystyle \sum_{i=l}^{r} \sum_{j=i}^{r} \sum_{k=i}^{j} a_k$$$. Since these values can be quite large, please output them modulo $$$10^9 + 7$$$

Input

The first line contains two integers denoting $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$)

The second line contains $$$N$$$ integers, $$$a_1, a_2, \dots, a_n$$$. ($$$0 \le a_i \le 10^9$$$)

The next $$$Q$$$ lines will each contain a single integer, $$$t$$$, denoting the type of the query. If $$$t$$$ is $$$1$$$, then it will be followed by two integers $$$l$$$ and $$$r$$$. If $$$t$$$ is $$$2$$$, then it will be followed by three integers $$$l$$$, $$$r$$$, and $$$v$$$. ($$$1 \le l \le r \le N, 1 \le v \le 10^9$$$)

In testcase $$$1$$$, $$$N, Q \le 500$$$.

In testcases $$$2 - 4$$$, $$$N, Q \le 5000$$$.

In testcases $$$5 - 9$$$, In every query of type $$$2$$$, it is guaranteed that $$$l_i = r_i$$$.

In testcase $$$10$$$, there are no queries of type $$$1$$$.

In testcases $$$11 - 20$$$, there are no further restrictions.

Output

For each query of type $$$1$$$, output a line containing its corresponding answer.

Example
Input
5 5
1 2 3 4 5
1 1 5
1 2 5
2 1 3 4
1 1 5
1 2 5
Output
105
70
193
110
Note

Idea: oursaco

Preparation: oursaco

Occurrences: Advanced 11