解题思路

设输入的整数为 $n$ （同时也是数组长度），我们要统计长度为 $n$ 的正整数数组 $a_1,\dots,a_n$ ，满足 $\forall\,1\le i\le n-1:\ \mathrm{lcm}(a_i,a_{i+1})=n$ 。

若 $\mathrm{lcm}(x,y)=n$ ，必然有 $x|n,\ y|n$ 。将 $n$ 的质因数分解写作

P3735.第3题-数组的构造

1000ms

Difficulty: 9

所属公司 : 美团

算法与标签>数学

小美有一个正整数 $n$ ，小美想要构造一个长度为 $n$ 的正整数数组 $a$ ，满足 $\forall 1 ≦i<n,lcm(a_i,a_{i+1})= n$ ，也就是对于数组任意相邻两项的最小公倍数都等于 $n$ 。

但是小美觉得这个问题太简单了，所以希望你帮他求出一共有多少个数组 $a$ 满足这个条件。

由于答案可能很大，请将答案对 $10^9+7$ 取模后输出。

输入一个正整数 $n (2 ≦ n ≦ 10^{18})$ 。

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

输入

输出

159196343

输入

预期输出（选填）