Соскучившись от жизни на ферме, коровы ушли в бродячий цирк.
И с ними готовится новое шоу.
Сцена для шоу представляет \(N\) платформ, размещённых по кругу.
На каждой платформе от \(1\) до \(N\) коров формируют стек (корова становится на корову).
По сигналу главного на манеже, все стеки параллельно "падают" по
часовой стрелке так, что нижняя корова стека не движется, корова на ней
движется на одну платформу по часовой стрелке, следующая корова - на две платформы
и т.д. В результате получаются новые стеки коров.
Главный на манеже думает, что шоу будет лучше, если после того, как стеки упадут,
новый стек на каждой платформе будет содержать такое же количество коров, что
и исходный стек на манеже. Мы называем конфигурацию стеков на манеже "магической",
если она удовлетворяет этому условию. Вычислите количество "магических" конфигураций.
Поскольку это число может быть очень большое, выведите его остаток по модулю
\(10^9 + 7\).
Две конфигурации считаются различными, если существует платформа, для которых
у этих двух конфигураций различное количество коров.
ФОРМАТ ВВОДА (файл gymnasts.in):
Ввод - олдно целое число, \(N\) (\(1 \leq N \leq 10^{12}\)).
ФОРМАТ ВЫВОДА (файл gymnasts.out):
Одно целое число - количество магических конфигураций по модулю \(10^9 + 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
6
|