#10229. 「一本通 6.6 例 4」古代猪文

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:SDOI 2010

猪王国的文明源远流长,博大精深。

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

iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载,那个朝代流传的猪文文字恰好为远古时期的 k 分之一,其中 k N 的一个正约数(可以是 1 N )。不过具体是哪 k 分之一,以及 k 是多少,由于历史过于久远,已经无从考证了。

iPig 觉得只要符合文献,每一种能整除 N k 都是有可能的。他打算考虑到所有可能的 k 。显然当 k 等于某个定值时,该朝的猪文文字个数为 \frac Nk 。然而从 N 个文字中保留下 \frac Nk 个的情况也是相当多的。iPig 预计,如果所有可能的 k 的所有情况数加起来为 P 的话,那么他研究古代文字的代价将会是 G P 次方。

现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字,所以你只需要告诉他答案除以 999911659 的余数就可以了。

输入格式

输入有且仅有一行:两个数 N,G ,用一个空格分开。

输出格式

输出有且仅有一行:一个数,表示答案除以 999911659 的余数。

样例

样例输入

4 2

样例输出

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