Cow Gymnasts#10416
Bored with farm life, the cows have sold all their earthly possessions and joined the crew of a traveling circus. So far, the cows have been given easy acts: juggling torches, walking tightropes, riding unicycles — nothing a handy-hoofed cow can't handle. However, the ringmaster wants to create a much more dramatic act for the next show.
The stage layout for the new act consists of platforms arranged in a circle. On each platform, between and cows must form a stack, one cow on top of another. When the ringmaster gives the signal, all stacks must simultaneously fall clockwise: the bottom cow in a stack stays in place, the cow above her moves one platform clockwise, the next cow moves two platforms clockwise, and so on. Being accomplished gymnasts, the cows are sure they will have no trouble with the technical side of this act. The stacks do not interfere with each other as they fall, so every cow lands on her intended platform. All cows that land on the same platform form a new stack, which does not fall over.
The ringmaster believes the act will be especially 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. Help the cows count the number of magical configurations. Since this number may be very large, print it modulo 10^9 + 7.
Two configurations are considered different if at least one platform is assigned a different number of cows.
One integer n~(1 \le n \le 10^{12}).
Print one integer — the number of magical configurations modulo 10^9 + 7.
For n = 4, the magical 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).
Example 1