Given an array of integers A1,A2,…,AN 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 109+7
1 x y: Add 1×2×3 to Ax, add 2×3×4 to Ax+1, …, add (i+1)×(i+2)×(i+3) to Ax+iand so on until Ay
2 x y: Subtract 1×2×3 from Ax, subtract 2×3×4 from Ax+1, …, subtract (i+1)×(i+2)×(i+3) from Ax+i and so on until Ay
The first line contains two integers N and M (1≤N,M≤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.
1 1 8
0 2 8
2 4 6
0 5 6
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=1974
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