Problem A
Another Query on Array Problem

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$

Input

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.

Output

For each query of type $0$, print the required answer in a single line.

Sample Clarification

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$

8 4
1 1 8
0 2 8
2 4 6
0 5 6

1974
462