Description
厌倦了农场生活的奶牛们卖掉了所有的财产，加入了一个巡回马戏团。到目前为止，奶牛们被分配了一些简单的表演：杂耍火炬、走钢丝、骑独轮车——没有什么是一头灵巧的奶牛无法应付的。然而，马戏团团长希望为他们的下一场演出创造一个更加戏剧性的表演。
新表演的舞台布局包括 N 个平台，排列成一个圆圈。在每个平台上，必须有 1 到 N 头奶牛堆叠成一摞，奶牛一头叠在另一头上面。当团长发出信号时，所有的堆叠必须同时顺时针倒下，使得堆叠底部的奶牛不动，她上面的奶牛移动一个平台顺时针，再上面的奶牛移动两个平台顺时针，依此类推。作为技艺高超的体操运动员，奶牛们知道她们在技术方面不会有任何问题。各个奶牛堆叠在倒下时不会相互“干扰”，因此每头奶牛都会落在目标平台上。所有落在平台上的奶牛会形成一个新的堆叠，这个堆叠不会倒下。
团长认为，如果堆叠倒下后，每个平台上的新堆叠包含的奶牛数量与原始堆叠相同，那么这个表演将特别戏剧化。我们称满足这一条件的堆叠大小为“魔法”配置。请帮助奶牛们计算魔法配置的数量。由于这个数字可能非常大，请计算其对 109+7 取模的结果。
如果两个配置在任何平台上分配的奶牛数量不同，则认为它们是不同的配置。
Input
输入是一个整数 N（1≤N≤1012）。
Output
输出一个整数，表示魔法配置的数量对 109+7 取模的结果。
HINT
对于 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)。