Proficient.
Put your skills to the test.

Problem summary

Concatenate the finite blocks 1; 1,2,1; 1,2,3,2,1; and so on. Answer q inclusive position-range sum queries modulo 1,000,000,007. Positions start at 1.

Constraints

1 ≤ q ≤ 10⁵; 1 ≤ l ≤ r ≤ 10¹⁸.

Worked example

An independently prepared example for this explanation.

3
8 16
10 20
17 21

19
26
15

Solution analysis

1. The block with peak k has length 2k−1 and sum k². The first k complete blocks therefore occupy k² positions. For a prefix ending at position x, binary-search the greatest k with k²≤x; only a partial block with peak k+1 remains.
2. The complete blocks contribute 1²+2²+…+k² = k(k+1)(2k+1)/6. Compute this modulo the prime using the modular inverse of 6. Let t=x−k² and h=k+1. If t≤h, the partial contribution is t(t+1)/2. Otherwise include the whole increasing side h(h+1)/2, then s=t−h decreasing values with sum sh−s(s+1)/2.
3. For prefix 16, four blocks are complete, contributing 1+4+9+16=30. Prefix 7 contains the first two complete blocks (sum 5) and 1,2,3 from the next block (sum 6). Thus the range [8,16] has sum 30−11=19. Answer each query by subtracting two prefix values and normalizing modulo the prime.

Why it works

The sum of the first k odd lengths is k², so the integer search identifies exactly the fully included blocks. Their square-sum formula and the increasing/decreasing arithmetic sums account for every remaining prefix element once. The usual prefix difference then includes exactly the requested positions.

Watch out. Avoid floating-point square-root rounding at square boundaries. Reduce factors before multiplying; do not form the cubic square-sum numerator in 64 bits. Prefix zero must return zero.

An independently written complete program with standard headers.

#include<iostream>
// Algorithm: The block with peak k has length 2k−1 and sum k².
using namespace std;
const long long mod=1000000007;
long long triangle(long long value){
    return (value%mod)*((value+1)%mod)%mod*500000004%mod;
}
long long prefix(long long position){
    long long low=0;
    long long high=1000000001;
    while(high-low>1){
        long long middle=(low+high)/2;
        if(middle*middle<=position){
            low=middle;
        }
        else{
            high=middle;
        }
    }
    long long complete=low;
    long long answer=complete%mod*((complete+1)%mod)%mod;
    answer=answer*((2*complete+1)%mod)%mod*166666668%mod;
    long long used=position-complete*complete;
    long long peak=complete+1;
    if(used<=peak){
        answer=(answer+triangle(used))%mod;
    }
    else{
        long long descending=used-peak;
        answer=(answer+triangle(peak)+descending%mod*(peak%mod)-triangle(descending))%mod;
    }
    return (answer+mod)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int queries;
    cin>>queries;
    while(queries--){
        long long left,right;
        cin>>left>>right;
        cout<<(prefix(right)-prefix(left-1)+mod)%mod<<'\n';
    }
}