Cow Gymnasts

题目描述

厌倦了农场生活，奶牛们卖掉了所有身外之物，加入了巡回马戏团的队伍。到目前为止，奶牛们被安排的节目都很简单：抛火把、走钢丝、骑独轮车——这些对灵巧的牛蹄来说都不在话下。然而，驯兽师希望在下一场演出中安排一个更加戏剧性的节目。

新节目的舞台布局由按圆形排列的 $N$ 个平台组成。在每个平台上，必须有 $1$ 到 $N$ 头奶牛叠成一摞，一头压一头。当驯兽师发出信号时，所有的牛摞必须同时按顺时针方向倒下：在一摞中，最底下的奶牛不移动；她上面的一头顺时针移动一个平台；再上面的一头顺时针移动两个平台；以此类推。作为技艺高超的体操运动员，奶牛们知道完成这个动作在技术上毫无问题。各个牛摞在倒下时不会互相“干扰”，因此每头奶牛都会落到预定的平台上。落在同一平台上的所有奶牛会形成新的一个牛摞，并且这个新牛摞不会继续倒下。

驯兽师认为，如果牛摞倒下后，每个平台上的新牛摞所含奶牛数量与该平台原本的牛摞相同，这个节目会格外戏剧性。若一个牛摞大小的配置满足这一条件，我们称其为“魔法的”。请帮助奶牛们计算魔法配置的数量。由于答案可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

若存在某个平台，使得两个配置在该平台分配的奶牛数量不同，则认为这两个配置不同。

输入格式

输入为一个整数 $N$（$1 \leq N \leq 10^{12}$）。

输出格式

输出一个整数，表示魔法配置的数量对 $10^9 + 7$ 取模后的结果。

4

6

提示

对于 $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)$。 Problem credits: Dhruv Rohatgi

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum