#include <cstdio>
#include <cassert>
#include <iostream>
using std::cin;
using std::cout;
using ll = long long;
namespace number_theory {
constexpr int MOD = 999911659;
int frac_[35616], *const frac = frac_ - 1;
static int init__ = []() {
    frac[1] = 1;

    for (int i = 2; i < 35617; i++) {
        frac[i] = frac[i - 1] * 1ll * i % (MOD - 1);
    }

    return 0;
}();
ll qp(ll x, ll t, int mod) {
    ll ans = 1;

    while (t) {
        if (t & 1)
            ans = (ans * x) % mod;

        x = x * x % mod;
        t >>= 1;
    }

    return ans;
}
ll lucas(ll n, ll m, ll p, bool noloop = false) {
    if (!m)
        return 1;

    if (n < m)
        return 0;

    if (n == m)
        return 1;

    if (!noloop)
        return lucas(n % p, m % p, p, true) * 1ll * lucas(n / p, m / p, p) % p;

    return frac[n] * 1ll * qp(frac[n - m], p - 2, p) % p * qp(frac[m], p - 2, p) % p;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    ll g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
void excrt(ll &a, ll &x, ll b, ll y) {
    ll n, m;
    ll g = exgcd(x, y, n, m);
    assert((b - a) % g == 0);
    n *= (b - a) / g;
    a = a + x * n;
    x = x * y / g;
    a %= x;
}
}
namespace m {
int in, ig;
using namespace number_theory;
int solve(int x) {
    ll a = 0, b, xx = 1, yy;

    for (int i : {
                2, 3, 4679, 35617
            }) {
        b = lucas(in, x, i);
        yy = i;
        excrt(a, xx, b, yy);
    }
    return a;
}
void work() {
    cin >> in >> ig;

    if (ig % MOD == 0) {
        cout << 0;
        return;
    }

    int ans = 0;

    for (int i = 1; i * i <= in; i++) {
        if (in % i)
            continue;

        ans += solve(i);
        ans %= (MOD - 1);

        if (i * i != in) {
            ans += solve(in / i);
            ans %= (MOD - 1);
        }
    }

    cout << qp(ig, (ans + MOD - 1) % (MOD - 1), MOD) << '\n';
}
}
int main() {
    m::work();
    return 0;
}