Коровьи гимнасты
Соскучившись от жизни на ферме, коровы ушли в бродячий цирк. И с ними готовится новое шоу.Сцена для шоу представляет n платформ, размещённых по кругу. На каждой платформе от 1 до n коров формируют стек (корова становится на корову). По сигналу главного на манеже, все стеки параллельно "падают" по часовой стрелке так, что нижняя корова стека не движется, корова на ней движется на одну платформу по часовой стрелке, следующая корова - на две платформы и т.д. В результате получаются новые стеки коров.
Главный на манеже думает, что шоу будет лучше, если после того, как стеки упадут, новый стек на каждой платформе будет содержать такое же количество коров, что и исходный стек на манеже. Мы называем конфигурацию стеков на манеже "магической", если она удовлетворяет этому условию. Вычислите количество "магических" конфигураций. Поскольку это число может быть очень большое, выведите его остаток по модулю 10^9 + 7.
Две конфигурации считаются различными, если существует платформа, для которых у этих двух конфигураций различное количество коров.
Входные данные
Одно целое число n (1 ≤ n ≤ 10^12).
Выходные данные
Одно целое число - количество магических конфигураций по модулю 10^9 + 7.
Пример
Для n = 4, корректные конфигурации: (1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3) и (3, 2, 3, 2).