题目描述

题目译自 eJOI2017 Problem C. Six

Elly 研究了对于一些给定的整数 $N$ 的性质。目前她发现了这个整数的质因子不超过六个。质数是指没有除 $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$。

输出格式

输出一个整数，表示对于 $N$ 的合法序列个数。因为这个整数可能很大，请输出这个整数对 $10^9+7$ 取模后的值。

6

28

所有 $28$ 种合法的序列如下：

$$\begin{aligned} (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) \end{aligned} $$

203021

33628

60357056536

907882

12156144

104757552

这组样例的答案为 $14104757650$，但你应该输出答案对 $10^9+7$ 取模后的值，因此最终结果为 $14104757650\bmod 1000000007=104757552$。

数据范围与提示

对于所有数据，$1\le N\le 10^{15}$。

• 对于约 $30\%$ 的数据，$N$ 至多有两个质因子；
• 对于约 $60\%$ 的数据，$N$ 至多有四个质因子；
• 对于所有数据，$N$ 至多有六个质因子。