410783: GYM104103 D The Name of the Fourth Problem

Consider an infinite sequence of integers $$$a_1, a_2, a_3, \ldots$$$. The sequence is called a self-describing if $$$a_i$$$ is equal to the number of occurrences of $$$i$$$ in this sequence.

If we restrict this sequence to satisfy $$$a_1 = 1$$$ and the numbers a non-decreasing (that is, $$$a_i \le a_{i+1}$$$ for all $$$i$$$), then the self-describing sequence is unique. The first thirty elements are as follows:

$$$$$$ 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, \ldots $$$$$$

Your task is to calculate the range sum queries for this sequence efficiently. Let's go!

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of range sum queries. The following $$$t$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{15}$$$) each. The $$$i$$$-th query requires you to calculate $$$\sum_{k=l_i}^{r_i} a_k$$$.

Print $$$t$$$ lines, each one with a single integer — the answer to the range sum query. Because the sum can be large, print it modulo $$$1\,000\,000\,007$$$.

5
1 1
2 2
3 4
56 56
5 13

1
2
5
14
42