#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>

#define int long long 
#define inf 0x3f3f3f3f

using namespace std;

const int N = 1e6 + 100;

int x, y, c1, c2, c3, c4;
int inv1[N], inv2[N], inv3[N], inv4[N];
int mod = 999911659;
int mod1 = 2, mod2 = 3, mod3 = 4679, mod4 = 35617;
int sumMod = mod - 1;

int mul(int a, int b, int mod) {
	int ans = 0;
	while (b) {
		if (b & 1) ans = (ans + a) % mod;
		a = (a + a) % mod;
		b >>= 1;
	}
	return ans;
}

int quick_pow(int a, int b, int mod) {
	int ans = 1;
	a = a % mod;
	while (b) {
		if (b & 1) ans = mul(ans, a, mod);
		a = mul(a, a, mod);
		b >>= 1;
	}
	return ans;
}


int C(int n, int m, int mod) {
	if (n < m) return 0;
	if (n == m) return 1;
	if (mod == mod1) return mul(inv1[n], mul(quick_pow(inv1[m], mod - 2, mod), quick_pow(inv1[n - m], mod - 2, mod), mod), mod);
	if (mod == mod2) return mul(inv2[n], mul(quick_pow(inv2[m], mod - 2, mod), quick_pow(inv2[n - m], mod - 2, mod), mod), mod);
	if (mod == mod3) return mul(inv3[n], mul(quick_pow(inv3[m], mod - 2, mod), quick_pow(inv3[n - m], mod - 2, mod), mod), mod);
	if (mod == mod4) return mul(inv4[n], mul(quick_pow(inv4[m], mod - 2, mod), quick_pow(inv4[n - m], mod - 2, mod), mod), mod);
	return 0;
}

int lucas(int n, int m, int mod) {
	if (m == 0) return 1;
	return lucas(n / mod, m / mod, mod) * C(n % mod, m % mod, mod);
}

void exgcd(int a, int b) {
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b);
	int temp = x;
	x = y;
	y = temp - (a / b) * y;
}

void init() {
	exgcd(sumMod / mod1, mod1);
	x = (x % mod1 + mod1) % mod1;
	c1 = (sumMod / mod1) * x;
	exgcd(sumMod / mod2, mod2);
	x = (x % mod2 + mod2) % mod2;
	c2 = (sumMod / mod2) * x;
	exgcd(sumMod / mod3, mod3);
	x = (x % mod3 + mod3) % mod3;
	c3 = (sumMod / mod3) * x;
	exgcd(sumMod / mod4, mod4);
	x = (x % mod4 + mod4) % mod4;
	c4 = (sumMod / mod4) * x;
	inv1[0] = inv2[0] = inv3[0] = inv4[0] = 1;
	int ret = 1e5;
	for (int i = 1; i <= ret; i++) {
		inv1[i] = inv1[i - 1] * i % mod1;
		inv2[i] = inv2[i - 1] * i % mod2;
		inv3[i] = inv3[i - 1] * i % mod3;
		inv4[i] = inv4[i - 1] * i % mod4;
	}
}

signed main() {
	int n, g, ans = 0;
	cin >> n >> g;
	init();
	int sum1 = 0;
	int sum2 = 0;
	int sum3 = 0;
	int sum4 = 0;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			int k = i;
			sum1 = (sum1 + lucas(n, k, mod1)) % mod1;
			sum2 = (sum2 + lucas(n, k, mod2)) % mod2;
			sum3 = (sum3 + lucas(n, k, mod3)) % mod3;
			sum4 = (sum4 + lucas(n, k, mod4)) % mod4;
			if (n == i * i) continue;
			k = n / i;
			sum1 = (sum1 + lucas(n, k, mod1)) % mod1;
			sum2 = (sum2 + lucas(n, k, mod2)) % mod2;
			sum3 = (sum3 + lucas(n, k, mod3)) % mod3;
			sum4 = (sum4 + lucas(n, k, mod4)) % mod4;
		}
	}
	ans = mul(sum1, c1, sumMod) + mul(sum2, c2, sumMod) + mul(sum3, c3, sumMod) + mul(sum4, c4, sumMod);
	ans %= sumMod;
	int output = quick_pow(g, ans, mod);
	cout << output << endl;
}