D. Моя милая девочка Нура
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В университете Павлополиса, где учится Нура, решили провести конкурс красоты «Мисс университета Павлополиса». Опишем подробнее процесс выбора самой красивой девушки в университете.

Конкурс проходит в несколько этапов. Пусть изначально в конкурсе участвует n девушек. Всех участниц делят на равные группы по x человек в каждой. При этом число x выбирается произвольно, то есть число x может быть различным для разных этапов конкурса. Внутри каждой группы жюри конкурса сравнивает девушек по красоте в формате «каждая с каждой». Таким образом, если в группе x девушек, то происходит сравнений. Затем из каждой группы выбирается по одной самой красивой участнице. Выбранные девушки попадают в следующий этап конкурса. То есть, если n девушек были разделены на группы, по x участниц в каждой, то в следующий этап попадут ровно участниц. Конкурс продолжается до тех пор, пока не останется ровно одна девушка, которая и будет признана «Мисс университета Павлополиса».

Но для жюри этот конкурс — очень утомительное занятие. Им хотелось бы делить девушек на группы в каждом этапе так, чтобы суммарное число попарных сравнений девушек было как можно меньше. Обозначим за f(n) минимальное суммарное количество сравнений, которые надо провести, чтобы выбрать самую красивую участницу, если к первому этапу допустить n девушек.

Организаторы конкурса — большие сумасброды. Они дают Нуре три целых числа t, l и r и просят бедную девушку посчитать значение следующего выражения: t0·f(l) + t1·f(l + 1) + ... + tr - l·f(r). Однако, так как значение этого выражения может быть достаточно велико, организаторы просят посчитать его по модулю 109 + 7. Если Нура сможет посчитать значение этого выражения, организаторы обещают ей помощь в ходе конкурса красоты. Но бедная девушка не сильна в математике, поэтому за помощью она обратилась к Лехе, а тот — прямиком к вам.

Входные данные

В первой и единственной строке задано три целых числа t, l и r (1 ≤ t < 109 + 7, 2 ≤ l ≤ r ≤ 5·106).

Выходные данные

Выведите единственное число — значение искомого выражения по модулю 109 + 7.

Пример
Входные данные
2 2 4
Выходные данные
19
Примечание

Рассмотрим пример.

Необходимо найти значение .

f(2) = 1. Из двух девушек можно составить только одну группу из двух человек, в которой произойдет одно сравнение.

f(3) = 3. Из трех девушек можно составить только одну группу из трех человек, в которой произойдет три сравнения.

f(4) = 3. Четырех девушек можно разбить на две группы по две девушки в каждой. Тогда на первом этапе произойдет два сравнения, по одному в каждой из двух групп. Во второй этап выйдут две девушки, между которыми произойдёт ещё одно сравнение. Итого 2 + 1 = 3. Можно также в первом этапе оставить всех девушек в одной группе. Тогда произойдет сравнений. Очевидно, что лучше разбивать девушек на группы первым способом.

Тогда значение выражения это .