// 思路: 先求出p,最后用快速幂求一下g^p即可
//       p = ∑d|n C(n,d) % (999911659)
//       先枚举n的所有约数,然后利用luca定理对式子求值
#include <bits/stdc++.h>
using namespace std;

using ll = long long ;
const int N = 1e5 + 50;
const ll p = 999911659;
ll fac[N]; // 记录阶乘
ll divfac[N]; // 记录逆元的阶乘
ll ksm(ll a,ll b,ll p) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret  * a % p;
		a = a * a % p ;
		b >>= 1;
	}
	return ret % p;
}

ll getc(ll a,ll b) { //c(a,b) = a!/b!(a-b)!
	if (b > a) return 0;
	return fac[a] * divfac[b] % p * divfac[a - b] % p;
}

ll lucas(ll a,ll b) { // 卢卡斯定理:c(a,b) = c(a/p,b/p)*c(a%p,b%p) % p
	if (b == 0) return 1; // 递归结束条件
	ll ans = lucas(a/p,b/p) * getc(a%p,b%p) % p;
	return  ans;
}
int main() {
    ll n,g; 
    cin >> n >> g;
    ll psum = (n + 1) % p;
    fac[0] = divfac[0] = 1;
    for (int i = 1;i <= n; i++) { // 预处理n以内的阶乘和逆元阶乘
    	fac[i] = fac[i - 1] * i % p;
    	divfac[i] = divfac[i - 1] * ksm(i,p - 2,p);
    }
    for (int i = 2;i <= n / i; i++) {
    	if (n % i == 0) {
    		psum = (psum + lucas(n,i) ) % p;
    		if (i != n / i) psum = (psum + lucas(n,n / i) ) % p;
    	}
    } 
    //cout << psum;
    cout << ksm(g,psum,p);
	return 0;
}