好的，我们重新整理为 LaTeX 数学格式：

题目描述

原题来自：SDOI 2010

猪王国的文明源远流长，博大精深。
iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 $N$。一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。

iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的 $\frac{1}{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$ 的余数就可以了。

输入格式

输入有且仅有一行：两个整数 $N, G$，用一个空格分开。

输出格式

输出有且仅有一行：一个整数，表示答案除以 $999911659$ 的余数。

样例

样例输入 1

4 2

样例输出 1

2048

样例解释 1

$N = 4$ 的正约数有 $1, 2, 4$。

• 当 $k = 1$ 时，保留文字个数为 $\frac{4}{1} = 4$，从 $4$ 个文字中选 $4$ 个，方案数为 $C(4,4) = 1$。
• 当 $k = 2$ 时，保留文字个数为 $2$，方案数为 $C(4,2) = 6$。
• 当 $k = 4$ 时，保留文字个数为 $1$，方案数为 $C(4,1) = 4$。

因此 $P = 1 + 6 + 4 = 11$。
所求代价为 $2^{11} = 2048$。
对 $999911659$ 取余后仍是 $2048$。

数据范围

• 对于 $10\%$ 的数据，$1 \le N \le 50$；
• 对于 $20\%$ 的数据，$1 \le N \le 1000$；
• 对于 $40\%$ 的数据，$1 \le N \le 10^5$；
• 对于 $100\%$ 的数据，$1 \le G \le 10^9$，$1 \le N \le 10^9$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

注意： 由于 $G$ 和 $P$ 都可能很大，需要使用数论组合数计算与扩展欧拉定理等技巧，避免直接计算大幂次。