猪王国的文明源远流长，博大精深。
iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 $N$ 。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。
iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的 $k$ 分之一，其中 $k$ 是 $N$ 的一个正约数（可以是 $1$ 和 $N$ ）。不过具体是哪 $k$ 分之一，以及 $k$ 是多少，由于历史过于久远，已经无从考证了。
iPig觉得只要符合文献，每一种能整除 $N$ 的 $k$ 都是有可能的。他打算考虑到所有可能的 $k$ 。显然当 $k$ 等于某个定值时，该朝的猪文文字个数为 $\frac{N}{k}$。然而从 $N$ 个文字中保留下 $\frac{N}{k}$ 个的情况也是相当多的。iPig预计，如果所有可能的 $k$ 的所有情况数加起来为 $P$ 的话，那么他研究古代文字的代价将会是 $G$ 的 $P$ 次方。
现在他想知道猪王国研究古代文字的代价是多少。由于iPig觉得这个数字可能是天文数字，所以你只需要告诉他答案除以999911659的余数就可以了。
链接
题解
依据题意推出式子
$$
t = \sum _ {k|N} C^{k} _ {N}\
ans = G^t
$$
我们有指数的一个性质
$$
a ^ b \equiv a ^ {b\ \bmod\ p-1} \pmod p
$$
也就是指数的循环节是 $p-1$ 。
所以我们只需要
$$
ans = G^t = G^{t\ \bmod\ (p-1)} \pmod p
$$
所以我们只需要算出 $t \bmod p-1$ 即可。
我们注意到 $p-1 = 999911659-1 = 2 \times 3 \times 4679 \times 35617$ ，分别 $Lucas$ 再 $CRT$ 合并即可。
事实上我们可以只做一次 $CRT$ ，即我们每次都算出在模某数意义下的 $t$ ，最后合并一次即可。
还要特判 $G = P$ 的情况。
时间复杂度大约是 $O(\sqrt n \times \log n )$ 。
代码
| |
