https://codeforces.me/blog/entry/55597

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

Input

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.

Output

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

Sample testcase:

Input

8 4

1 1 8

0 2 8

2 4 6

0 5 6

Ouput

1974

462

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