Given an array of integers $A_1, A_2, \ldots , A_ N$ and the initial value of all elements are $0$. Now you are given $M$ queries, each belongs to one of three following types:
$0$ $x$ $y$: Find the sum of all elements from index $x$ to index $y$ modulo $10^9+7$
$1$ $x$ $y$: Add $1 \times 2 \times 3$ to $A_ x$, add $2 \times 3 \times 4$ to $A_{x+1}$, …, add $(i+1) \times (i + 2) \times (i+3)$ to $A_{x+i}$ and so on until $A_ y$
$2$ $x$ $y$: Subtract $1 \times 2 \times 3$ from $A_ x$, subtract $2 \times 3 \times 4$ from $A_{x+1}$, …, subtract $(i+1) \times (i+2) \times (i+3)$ from $A_{x+i}$ and so on until $A_ y$
The first line contains two integers $N$ and $M$ ($1 \leq N, M \leq 10^5$) - the size of the array and the number of queries, respectively.
Each of the next M lines containts three integers $t$ $x$ $y$ denotes type and range of the query.
For each query of type $0$, print the required answer in a single line.
In the example below:
After the first query, the array is $[6, 24, 60, 120, 210, 336, 504, 720]$.
The answer for the second query is $24+60+120+210+336+504+720=1\, 974$.
After the third query, the array is $[6, 24, 60, 114, 186, 276, 504, 720]$.
The answer for the last query is $186+276=462$
Sample Input 1 | Sample Output 1 |
---|---|
8 4 1 1 8 0 2 8 2 4 6 0 5 6 |
1974 462 |