[eJOI2017] 六
题目描述
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)$ 的值。
输入输出样例
输入样例 #1
6
输出样例 #1
28
输入样例 #2
203021
输出样例 #2
33628
输入样例 #3
60357056536
输出样例 #3
907882
输入样例 #4
12156144
输出样例 #4
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](www.ejoi.org) Problem B [Six](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/six_statement-en.pdf)
翻译提供:@[```_Wallace_```](https://www.luogu.com.cn/user/61430)