Пусть \(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}\).
В первой строке дано число \(q\) — число запросов (\(1 \leq q \leq 10^5\)).
В следующих \(q\) строках заданы два числа \(l_i\), \(r_i\) — границы отрезка \(i\)-го запроса (\(4 \leq l_i \leq r_i \leq 10^{18}\)).
Для каждого запроса выведите ответ на него по модулю \(10^9 + 7\).
В таблице снизу приведены значения функций \(f\)(\(x\)) и \(g\)(\(x\)) при целых \(x\), таких что \(1 \leq x \leq 8\).
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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач