题目内容

在某个遥远的星系中，每一种恒星的“能量印记”都可以用一个正整数表示。对于两个能量印记 $x$ 和 $y$，它们的“共鸣值”定义为：将 $x$ 和 $y$ 分别分解质因数后，每个质数的指数取两者中的较大值，连乘得到的新数（即如果 $x = \prod p_i^{a_i}$，$y = \prod p_i^{b_i}$，则共鸣值为 $\prod p_i^{\max(a_i,b_i)}$）。科学家发现了一个古老的“枢纽常数” $M$，他们希望构造一个长度为 $M$ 的序列 $A_1, A_2, \dots, A_M$，其中每一项都是一个正整数，且满足任意相邻两项的共鸣值恰好都等于 $M$。请你计算满足条件的序列共有多少种。因为答案可能非常大，请输出结果对 $10^9+7$ 取模后的值。

$M$ 的范围为 $2 \le M \le 10^{18}$。

输入描述

输入包含一行，一个正整数 $M$。

输出描述

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