题目描述

Bored of farm life, the cows have sold all their earthly possessions and joined the crew of a traveling circus. So far, the cows had been given easy acts: juggling torches, walking tightropes, riding unicycles -- nothing a handy-hoofed cow couldn't handle. However, the ringmaster wants to create a much more dramatic act for their next show. The stage layout for the new act involves $N$ platforms arranged in a circle. On each platform, between $1$ and $N$ cows must form a stack, cow upon cow upon cow. When the ringmaster gives the signal, all stacks must simultaneously fall clockwise, so that the bottom cow in a stack doesn't move, the cow above her moves one platform clockwise, the next cow moves two platforms clockwise, and so forth. Being accomplished gymnasts, the cows know they will have no trouble with the technical aspect of this act. The various stacks of cows will not "interfere" with each other as they fall, so every cow will land on the intended platform. All of the cows landing on a platform form a new stack, which does not fall over.

The ringmaster thinks the act will be particularly dramatic if after the stacks fall, the new stack on each platform contains the same number of cows as the original stack on that platform. We call a configuration of stack sizes "magical" if it satisfies this condition. Please help the cows by computing the number of magical configurations. Since this number may be very large, compute its remainder modulo $10^9 + 7$.

Two configurations are considered distinct if there is any platform for which the configurations assign a different number of cows.

输入格式

The input is a single integer, $N$ ($1 \leq N \leq 10^{12}$).

输出格式

A single integer giving the number of magical configurations modulo $10^9 + 7$.

题目大意

厌倦了农场生活，奶牛们变卖了所有尘世的财产，加入了一支巡回马戏团。到现在为止，奶牛们已经能够进行简单的表演了：耍火把、走钢丝、骑独轮车——没什么是拥有灵巧蹄子的奶牛做不到的。但是，马戏团指挥想要为他们的下一次演出创作一个更加激动人心的表演。

新的表演所用的舞台由$N$个围成一圈的平台组成。在每个平台上，$1$至$N$头奶牛叠成一摞，一头叠在一头上面。当指挥给出信号的时候，每摞奶牛同时顺时针落下，最下面的奶牛不动，在她上面的奶牛顺时针移动一个平台，再上面的奶牛顺时针移动两个平台，等等。作为技艺高超的体操家，奶牛们明白她们在这个表演的技术方面没有任何问题。不同摞的奶牛在下落的过程中不会相互“干扰”，所以每头奶牛都会落在预期的平台上。然后所有落在同一平台上的奶牛又会重新叠成一摞，这次她们不会再落下来。

指挥认为，如果在奶牛们落下之后，每个平台上新的那一摞奶牛的数量和原来这个平台上的那一摞奶牛数量相等的话，这次表演就会格外激动人心。我们把满足这种性质的各摞奶牛的数量排列称为是“魔幻的”。请帮助奶牛计算魔幻的排列数。由于这个数字可能非常大，计算该数mod $10^9 + 7$的余数。

两个排列被认为是不同的，如果这两个排列在任何一个平台上分配了不同数量的奶牛。

输入格式（文件名：gymnasts.in）： 输入包含一个整数$N$（$1 \leq N \leq 10^{12}$）。

输出格式（文件名：gymnasts.out）： 输出一个整数，为魔幻的排列数mod $10^9 + 7$的余数。

4

6

提示

For $N = 4$, the valid configurations are $(1,1,1,1)$, $(2,2,2,2)$, $(3,3,3,3)$, $(4,4,4,4)$, $(2,3,2,3)$, and $(3,2,3,2)$.

Problem credits: Dhruv Rohatgi