Пусть \(f\)(\(x\)) — это округленный вниз двоичный логарифм \(x\). То есть \(f\)(\(x\)) — наибольшее такое целое неотрицательное число \(y\), что \(2^y\) не превосходит \(x\).
Пусть \(g\)(\(x\)) — это округленный вниз логарифм числа \(x\) по основанию \(f\)(\(x\)). То есть \(g\)(\(x\)) — наибольшее такое целое неотрицательное число \(z\), что \({f(x)}^{z}\) не превосходит \(x\).
Вам даны \(q\) запросов. \(i\)-й запрос выглядит как два числа \(l_i\), \(r_i\). Ответом на запрос является сумма \(g\)(\(k\)) по всем целым положительным \(k\) таким, что \(l_i \leq k \leq r_i\). Ответы на запросы выводите по модулю \({10^9 + 7}\).
Выходные данные
Для каждого запроса выведите ответ на него по модулю \(10^9 + 7\).
Примечание
В таблице снизу приведены значения функций \(f\)(\(x\)) и \(g\)(\(x\)) при целых \(x\), таких что \(1 \leq x \leq 8\).
| \(x\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) |
| \(f\) | \(0\) | \(1\) | \(1\) | \(2\) | \(2\) | \(2\) | \(2\) | \(3\) |
| \(g\) | \(-\) | \(-\) | \(-\) | \(2\) | \(2\) | \(2\) | \(2\) | \(1\) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625
|
6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692
|