#P10387. [2021年联测]箱子

    ID: 9505 传统题 1000ms 256MiB 尝试: 6 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-不变量分析裴蜀等式置换循环分解乘法原理欧拉函数试除法分解质因数快速幂

[2021年联测]箱子

题目背景

有 n n 个围成一圈的平台,每个平台上有 1 1 至 n n 个箱子叠成一摞,一个箱子叠在另一个箱子上。

此时平台周围发生了地震,每摞箱子都同时向顺时针方向倒去。每摞的第一个箱子不动,第二个箱子顺时针移动一个平台,第三个箱子顺时针移动两个平台,等等。你需要求出有多少种放箱子的方法,满足每个平台上的箱子个数在地震后仍然保持不变。

由于答案可能很大,你只需要输出答案对 109+7 10^9 + 7 取模的结果即可。

输入格式

输入一个正整数 n n 。

输出格式

输出一个整数,表示答案对 109+7 10^9 + 7 取模的结果。

样例输入 1
4
样例输出 1
6
样例解释 1

有 $(1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3), (3, 2, 3 , 2)$ 六种方法。

数据范围与约定

对于所有数据,满足 1≤n≤1012 1 \le n \le 10^{12} 。

subtask1(1010 分):n≤9 n \le 9 。

subtask2(2020 分):n≤106 n \le 10^6 。

subtask3(7070 分):无特殊限制。