题目描述

题目译自 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

203021

33628

60357056536

907882

12156144

104757552

数据范围与提示

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

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