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

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

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

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