80分，rt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 999911659, MOD2 = 999911658;
const ll p[4] = {2, 3, 4679, 35617};
//999911658=2*3*4679*35617
ll n, g, c[4][35618];
ll qpow(ll x, ll y, ll z){
	if (!y) return 1;
	ll t = qpow(x, y / 2, z);
	t = t * t % z;
	if (y & 1) t = t * x % z;
	return t; 
}
ll inv(ll x, ll y){
	return qpow(x, y - 2, y);
}
ll C(ll x, ll y, int i){ //mod p[i]
	ll ans = c[i][x] * inv(c[i][x - y], p[i]) % p[i] * inv(c[i][y], p[i]) % p[i];
	return ans;
}
ll Lucas(ll x, ll y, int i){
	if (x < p[i] && y < p[i]){
		return C(x, y, i);
	}
	return Lucas(x / p[i], y / p[i], i) * Lucas(x % p[i], y % p[i], i) % p[i];
}
ll exgcd(ll a, ll b, ll &x, ll &y){
	if (!b){
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, x, y);
	ll z = x; x = y, y = z - y * (a / b);
	return d;
}
struct Node{ll a, m;};
Node CRT(Node x, Node y){
	ll a1 = x.a, m1 = x.m, a2 = y.a, m2 = y.m;
	ll u1, u2; exgcd(m1, m2, u1, u2);
	ll m = m1 * m2;
	ll a = (((a2*m1%m*u1%m+m)%m + (a1*m2%m*u2%m+m)%m) % m + m) % m;
	return (Node){a, m}; 
}
ll solve(ll x, ll y){ //C(x,y) mod MOD2
	Node ans = (Node){Lucas(x, y, 0), p[0]};
	for (int i = 1; i < 4; i++){
		Node now = (Node){Lucas(x, y, i), p[i]};
		ans = CRT(ans, now);
	}
	return ans.a;
}
ll ss = 0;
signed main(){
	scanf("%lld%lld", &n, &g);
	if (!(g % MOD)){
		puts("0");
		return 0;
	}
	c[0][0] = c[1][0] = c[2][0] = c[3][0] = 1;
	for (ll i = 1; i <= 35617; i++){
		for (int j = 0; j < 4; j++){
			c[j][i] = c[j][i - 1] * i % p[j];
		}
	}
	for (ll d = 1; d * d <= n; d++){
		if (!(n % d)){
			ss = (ss + solve(n, d)) % MOD2;
			if (d * d != n){
				ss = (ss + solve(n, n / d)) % MOD2;
			}
		}
	}
	ll ans = qpow(g, ss, MOD);
	printf("%lld\n", ans);
	return 0;
}