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

The above is the subject and the bottom is my code. I don't understand why it wrong answer. Can you explain to me? Thank you!

#include <bits/stdc++.h> using namespace std;

define ll long long

define mod 1000000007

ll arr[100006]; ll t[262200]; ll lazy[262200];

void build(ll node, ll a, ll b) { if(a>b) return; if (a==b) { t[node]=arr[a]; return; }

build(node*2, a, (a+b)/2);
build(node*2+1,(a+b)/2+1,b);

t[node]=t[node*2]+t[node*2+1];

}

ll query(ll node, ll a, ll b, ll i, ll j) { if(a>b||a>j||b<i) return 0; if (lazy[node] !=0 ) { t[node]+= (lazy[node]*(b-a+1)); if (a!=b) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; }

if (a>=i && b<=j) return t[node];

ll q1=query(node*2, a, (a+b)/2, i, j);
ll q2=query(node*2+1, (a+b)/2+1, b, i, j);

return q1+q2;

}

void update(ll node, ll a, ll b, ll i, ll j, ll inc) { if(a>b) return; if (lazy[node]!=0) { t[node]+=lazy[node]*(b-a+1); if (a!=b) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; } if(a>b||a>j||b<i) return;

if (a>=i && b<=j)
{
    t[node]+= (inc*(b-a+1)) % mod;
    if (a!=b)
    {
        lazy[node*2]+= (inc % mod);
        lazy[node*2+1]+= (inc % mod);
    }
    return;
}

update(node*2, a, (a+b)/2, i, j, inc);
update(node*2+1, (a+b)/2+1, b,i, j, inc);
t[node] = t[node*2] + t[node*2+1];

} int main(int argc, char const *argv[]) { ios_base::sync_with_stdio(0); ll t,n,m,q,p,a;

cin>>n>>m;
    build(1,0,n-1);
    memset(lazy, 0, sizeof(lazy));
    while(m--)
    {
        cin>>a>>p>>q;
        if (a==0)
        {
            cout<< query(1,0,n-1,p-1,q-1) % mod<<endl;
        }
        else if(a == 1)
        {
            ll cnt = 0, res;
            for(int t = p-1; t <= q-1; t++){
                res = ((cnt + 1) * (cnt + 2) * (cnt + 3)) % mod;
                update(1,0,n-1,t,t,res);
                cnt++;
            }

        }
        else if(a == 2)
        {
            ll cnt = 0, res;
            for(int t = p-1; t <= q-1; t++){
                res = ((cnt + 1) * (cnt + 2) * (cnt + 3)) % mod;
                update(1,0,n-1,t,t, -res);
                cnt++;
            }
        }
    }


return 0;

}