题目背景

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

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

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

输入格式

输入一个正整数 $n$。

输出格式

输出一个整数，表示答案对 $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 \le n \le 10^{12}$。

subtask1（$10$ 分）：$n \le 9$。

subtask2（$20$ 分）：$n \le 10^6$。

subtask3（$70$ 分）：无特殊限制。