2911. [USACO Feb18] 奶牛体操运动员

【题目描述】

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

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

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

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

【输入格式】

输入包含一个整数$N$（$1≤N≤10^{12}$）。

【输出格式】

输出一个整数，为魔幻的排列数mod $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)$。

【来源】

USACO Feb18 Platinum Cow Gymnasts

供题：Dhruv Rohatgi