# NT04 - Editorial

Difficulty

Hard

Problem

Solution

Lets define sum1 = (\sum i)\cdot (\sum i^2)
\Rightarrow sum1 = \sum i^3 + \sum \sum_{i\neq j} i^2\cdot j
\Rightarrow \sum \sum_{i\neq j} i^2\cdot j = sum1 -\sum i^3

Lets define sum2 = (\sum i)^3
\Rightarrow sum2 = \sum i^3 + 3\cdot \sum \sum_{i\neq j} i^2\cdot j + 6\sum \sum \sum_{i<j<k} i\cdot j\cdot k
\Rightarrow sum2 = \sum i^3 + 3\cdot (sum1 - \sum i^3) + 6\sum \sum \sum_{i<j<k} i\cdot j\cdot k
\Rightarrow 6\sum \sum \sum_{i<j<k} i\cdot j\cdot k = sum2 - 3\cdot sum1 + 2\cdot \sum i^3
\Rightarrow \sum \sum \sum_{i<j<k} i\cdot j\cdot k = (sum2 - 3\cdot sum1 + 2\cdot \sum i^3)/6

Clearly we can find out the value of all the terms in the right hand side by using some standard series formulas.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod ll(1e9+7)
ll cross(ll a,ll b){
a%=mod;
b%=mod;
return a*b%mod;
}
ll modexp(ll x,ll n,ll M)
{
if(n==0)
return 1;
if(n%2==0)
return modexp(x*x%mod,n/2,M);
return x*modexp(x*x%mod,(n-1)/2,M)%M;
}
ll modinverse(ll A,ll M)
{
return modexp(A,M-2,M);
}
int main()
{
int T;
cin>>T;
ll c6=modinverse(6,mod);
while(T--)
{
ll l,r;
cin>>l>>r;
ll fact1=r*(r+1)/2-l*(l-1)/2;
fact1%=mod;
ll fact2=cross(r,cross(r+1,2*r+1))*c6%mod - cross(l-1,cross(l,2*l-1))*c6%mod;
fact2=(fact2+mod)%mod;
ll sum1=fact1*fact2%mod;
sum1*=3;
sum1%=mod;
ll fact3=r*(r+1)/2-l*(l-1)/2;
fact3%=mod;
ll sum2=cross(fact3,cross(fact3,fact3));
ll imp1=r*(r+1)/2;
ll imp2=l*(l-1)/2;
imp1%=mod;
imp2%=mod;
ll sum3=(cross(imp1,imp1)-cross(imp2,imp2)+mod)%mod;
sum3=sum3*2;
sum3%=mod;
ll ans=(sum2+sum3-sum1+mod)%mod;
ans=(ans*c6)%mod;
cout<<ans<<"\n";
}
return 0;
}


P.S.

This problem can be solved by finding out the general term also, which i think will be some polynomial of order 5.