【例题3】古代猪文

题目描述

猪王国的文明源远流长，博大精深。$iPig$在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为$n$。$iPig$打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的$k$分之一，其中$k$是$n$的一个正约数（可以是$1$和$n$）。不过具体是哪$k$分之一，以及$k$是多少，由于历史过于久远，已经无从考证了。

$iPig$觉得只要符合文献，每一种能整除$n$的$k$都是有可能的。当$k$等于某个定值时，该朝的猪文文字个数为$\frac{n}{k}$。$iPig$预计，如果所有可能的$k$的所有情况数加起来为$p$的话，那么他研究古代文字的代价将会是$g$的$p$次方。现在他想知道猪王国研究古代文字的代价是多少。由于$iPig$觉得这个数字可能是天文数字，所以你只需要告诉他答案除以$999911659$的余数就可以了。

输入格式

输入有且仅有一行：两个数$n$，$g$，用一个空格分开。

输出格式

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

数据范围与提示

• 对于$10\%$的数据，$1 < n < 50$；
• 对于$20\%$的数据，$1 < n < 1000$；
• 对于$40\%$的数据，$1 \leq n \leq 10^{5}$；
• 对于$100\%$的数据，$1 \leq g \leq 10^{9}$，$1 \leq n \leq 10^{9}$。

样例

4 2

2048