Sums

Let $n=R-L+1$.

Consider sums made by choosing exactly $k$ values. Their minimum and maximum are

$$\operatorname{lo}_k=kL+\frac{k(k-1)}2, \qquad \operatorname{hi}_k=kR-\frac{k(k-1)}2.$$

When $k$ distinct values are chosen from consecutive integers, every integer between these two bounds is attainable. Thus the sums form the integer interval $I_k=[\operatorname{lo}_k,\operatorname{hi}_k]$.

Both endpoints increase with $k$. Therefore, the union size equals the sum of all interval lengths minus the overlaps of consecutive intervals.

The length of $I_k$ is

$$\operatorname{hi}_k-\operatorname{lo}_k+1=k(n-k)+1.$$

The sum of all interval lengths is

$$\sum_{k=1}^{n}(k(n-k)+1)=\frac{n(n+1)(n-1)}6+n.$$

The overlap length of $I_k$ and $I_{k+1}$ is

$$\max(0,\operatorname{hi}_k-\operatorname{lo}_{k+1}+1) =\max(0,k(n-1-k)-L+1).$$

It is positive exactly when $k(n-1-k)\geq L$.

The expression $k(n-1-k)$ increases for $k=1,2,\ldots,\lfloor(n-1)/2\rfloor$. Binary search for the smallest satisfying value . By symmetry, all satisfying indices are

$$a\leq k\leq n-1-a.$$

If no such value exists, the overlap sum is zero.

Let $b=n-1-a$. The total overlap to subtract is

$$\sum_{k=a}^{b}\left(k(n-1-k)-L+1\right) =(n-1)\sum_{k=a}^{b}k-\sum_{k=a}^{b}k^2-(L-1)(b-a+1).$$

This is evaluated in $O(1)$ using the standard formulas for $\sum k$ and $\sum k^2$.

All arithmetic for the answer is performed modulo $10^9+7$. Use 128-bit integers for products in the binary-search comparisons.

The time complexity per test case is $O(\log(R-L+1))$, and the additional space complexity is $O(1)$.

Solution written by GPT6