题目描述
原题来自：SDOI 2010
猪王国的文明源远流长，博大精深。
iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为
N
N。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。
iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的
k
k 分之一，其中
k
k 是
N
N 的一个正约数（可以是
1
1 和
N
N）。不过具体是哪
k
k 分之一，以及
k
k 是多少，由于历史过于久远，已经无从考证了。
iPig 觉得只要符合文献，每一种能整除
N
N 的
k
k 都是有可能的。他打算考虑到所有可能的
k
k。显然当
k
k 等于某个定值时，该朝的猪文文字个数为N/K 。然而从
N
N 个文字中保留下N/K个的情况也是相当多的。iPig 预计，如果所有可能的
k
k 的所有情况数加起来为
P
P 的话，那么他研究古代文字的代价将会是
G
G 的
P
P 次方。
现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字，所以你只需要告诉他答案除以
999911659
999911659 的余数就可以了。
输入
输入有且仅有一行：两个数
N,G
N,G，用一个空格分开。
输出
输出有且仅有一行：一个数，表示答案除以
999911659
999911659 的余数。
样例输入
4 2
样例输出
2048
提示
数据范围与提示
10\%
10% 的数据中，
1\le N\le 50
1≤N≤50；
20\%
20% 的数据中，
1\le N\le 1000
1≤N≤1000；
40\%
40% 的数据中，
1\le N\le 10^5
1≤N≤105；
100\%
100% 的数据中，
1\le G\le 10^9
1≤G≤109，
1\le N\le 10^9
1≤N≤109。
来源/分类
ybttg 组合计数 数论