题目描述

Elly 正在研究关于 正整数 $N$ 的一些性质，发现 $N$ 有不多于 $6$ 个不同的质因数。

接下来，她以一种特定的方式来生成的一个列表，一开始列表为空。她先写下了 $N$ 的一个大于一的因数 $x$ ，加入列表前，她先要确保 在所有已经在列表中的数中， 不能有 超过 $1$ 个 数与 $x$ 不互质。

举个例子，当 $N=12156144$ 时：

合法的列表有： $ (42), (616, 6, 91, 23),(91, 616, 6, 23), (66, 7), (66, 7, 7, 23, 299, 66), \\(143, 13, 66),(42,12156144),\text{etc.} $

而不合法的有：之一是 $(5,11)$，原因是 $5$ 不是 $N$ 的因子；还有一个是 $(66, 13, 143)$ ，原因是 $143$ 与其他两个数都不互质。

现在 Elly 希望你计算出给定的 $N$，可以生成几个不同的合法的列表。

若两个列表长度不同，或存在一个位置使得两个列表的该位置的值不同，那么我们说这两个列表不同的。

输入格式

一个整数：$N$。

输出格式

一个整数，表示列表的个数 $\bmod (10^9+7)$ 的值。

6

28

203021

33628

60357056536

907882

12156144

104757552

提示

【输入输出样例解释】

样例 1 解释

满足条件的列表有：$(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)$

以上共 $28$ 种。

样例 4 解释

真正的答案为 $14104757650$。

输出 $14104757650 \bmod (10^9+7)=104757552$

【数据规模与约定】

• 对于所有数据，保证 $1\le N\le 10^{15}$
• 对于约 $30\%$ 的数据，保证 $N$ 至多有 $2$ 个质因数。
• 对于约 $60\%$ 的数据，保证 $N$ 至多有 $4$ 个质因数。
• 对于 $100\%$ 的数据，保证 $N$ 至多有 $6$ 个质因数。

【说明】

原题来自：eJOI 2017 Problem B Six

翻译提供：@_Wallace_