解题思路

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

1）将问题转化到因子与质因数分解

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

题目内容

小美有一个正整数 $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$ 取模后的结果。

样例1

输入

114514

输出

159196343