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

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

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

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

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

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

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

【数据规模】

一本通