题目描述

小码哥最近在玩一款卡牌游戏，游戏中有许多种不同效果的卡牌，玩家需要在探险中收集卡牌，用收集来的卡牌进行战斗，直至探险旅途的终点。 小码哥在这次探险中，卡组有$n$张卡牌，卡组中没有两张卡牌是相同的。他遭遇了一次坠落事件，坠落事件会随机摔落卡组中的一些卡牌，使卡组大小恰好为原来卡组大小的$\frac{1}{k}$，其中$k$是$n$的正约数，可以是$1$和$n$，也就是说，坠落事件可以一张牌都没有摔掉，也可能把卡组直接削减到只剩一张牌! 由于小码哥还不知道坠落事件的影响，所以他需要考虑到所有可能的$k$，对于一种可能的$k$，事件过后小码哥的卡组大小将变为$\frac{n}{k}$，然而这$\frac{n}{k}$张卡牌也有许多不同的情况，小码哥预计，如果所有可能的$k$的所有卡组剩余卡牌的情况数之和为$S$的话，他付出的代价为$g^S$。 现在你知道小码哥的卡组大小为$n$，请你帮他计算这次坠落事件的代价，由于这个数可能很大，你只需要输出在模$999911659$下的结果即可。

输入格式

输入一行两个正整数$n,g$。

输出格式

输出一行一个整数表示你的答案。

样例输入 #1

4 2

样例输出 #1

2048

说明/提示

有$1\leq n,g\leq 10^9$。