Назар, ученик научного лицея Королевства Кремляндия, известен своими выдающимися математическими способностями. Сегодня учитель математики дал ему очень сложную задачу.
Рассмотрим два бесконечных множества чисел. Первое состоит из нечётных положительных чисел (\(1, 3, 5, 7, \ldots\)), а второе — из чётных положительных чисел (\(2, 4, 6, 8, \ldots\)). На первом этапе учитель выписывает на бесконечную доску первое число из первого множества, на втором этапе — первых два числа из второго множества, на третьем этапе — следующих четыре числа из первого множества, на четвёртом — следующих восемь чисел из второго множества и так далее. Другими словами, на каждом этапе, начиная со второго, он выписывает в два раза больше чисел, чем на предыдущем, а также меняет множество, из которого эти числа выписываются, на другое.
Десять первых выписанных чисел: \(1, 2, 4, 3, 5, 7, 9, 6, 8, 10\). Пронумеруем выписанные числа, начиная с единицы.
Задача состоит в том, чтобы по заданным числам \(l\) и \(r\) находить сумму чисел с номерами от \(l\) до \(r\). Ответ может получиться большим, так что нужно найти его остаток от деления на \(1000000007\) (\(10^9+7\)).
Назар очень долго думал над этой задачей, но так и не придумал решение. Помогите ему решить эту задачу.
Примечание
В первом примере ответом является сумма первых трёх выписанных чисел (\(1 + 2 + 4 = 7\)).
Во втором примере числа с номерами от \(5\) до \(14\): \(5, 7, 9, 6, 8, 10, 12, 14, 16, 18\). Их сумма равна \(105\).