Elly 正在研究给定整数 $N$ 的性质。到目前为止，她发现 $N$ 最多有 6 个不同的质因数。质数（或素数）是指大于 1 的自然数，除了 1 和它本身以外没有其他正约数。

现在，她按照以下方式打发时间：从一个空列表开始，她依次写下 $N$ 的大于 1 的约数（某些约数可以重复多次）。在向列表中添加一个新数字时，她确保该数字与已写下的数字中至多一个数字有大于 1 的公约数。

例如，如果 $N = 12156144$，她可以生成的许多有效序列中的一部分包括：$(42)$、$(616, 6, 91, 23)$、$(91, 616, 6, 23)$、$(66, 7)$、$(66, 7, 7, 23, 299, 66)$、$(143, 13, 66)$ 和 $(42, 12156144)$。无效序列的例子包括 $(5, 11)$（因为 5 不是 $12156144$ 的约数），或者 $(66, 13, 143)$（因为 143 与 13 和 66 都有公约数）。

现在 Elly 想知道 $N$ 的约数共有多少种不同的有效序列。如果两个序列的长度不同，或者在某个位置上的数字不同，我们就认为它们是不同的序列。

输入格式

从标准输入的第一行读取一个整数 $N$。

输出格式

在标准输出上打印一个整数，即 Elly 可能写出的 $N$ 的不同有效序列的数量。由于这个数字可能非常大，你只需要输出它除以 $1\,000\,000\,007$ 的余数。

数据范围

• $1 \le N \le 10^{15}$
• 在约 30% 的测试中，$N$ 最多有 2 个不同的质因数。
• 在约 60% 的测试中，$N$ 最多有 4 个不同的质因数。
• 在 100% 的测试中，$N$ 最多有 6 个不同的质因数。

样例

输入格式 1

6

输出格式 1

28

说明

第一个样例中所有 28 个有效序列为：$\{(2), (2, 2), (2, 2, 3), (2, 2, 3, 3), (2, 3), (2, 3, 2), (2, 3, 2, 3), (2, 3, 3), (2, 3, 3, 2), (2, 6), (2, 6, 3), (3), (3, 2), (3, 2, 2), (3, 2, 2, 3), (3, 2, 3), (3, 2, 3, 2), (3, 3), (3, 3, 2), (3, 3, 2, 2), (3, 6), (3, 6, 2), (6), (6, 2), (6, 2, 3), (6, 3), (6, 3, 2), (6, 6)\}$

输入格式 2

203021

输出格式 2

33628

输入格式 3

60357056536

输出格式 3

907882

输入格式 4

12156144

输出格式 4

104757552

说明

在最后一个样例中，答案是 $14104757650$，但由于要求输出对 $1\,000\,000\,007$ 取模的结果，实际结果为 $14104757650 \pmod{1000000007} = 104757552$。