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.

Problem credits: Dhruv Rohatgi

Problem credits: Dhruv Rohatgi

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\).

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Platinum