#include <bits/stdc++.h>
using namespace std;
long long f(long long a, long long b, long long p) {
    long long t = 1, y = a;
    while (b) {
        if (b & 1)
            t = t * y % p;
        y *= y;
        y %= p;
        b >>= 1;
    }
    return t;
}
long long reverse(long long x, long long p) { return f(x, p - 2, p); }
long long C(long long n, long long m, long long p) {
    long long a = 1, b = 1;
    if (n < m)
        return 0;
    if (m == 0)
        return 1;
    for (int i = n - m + 1; i <= n; i++) {
        a = a * i % p;
    }
    for (int i = 1; i <= m; i++) {
        b = b * i % p;
    }
    return a * reverse(b, p) % p;
}
long long Lucas(long long n, long long m, long long p) {
    if (m == 0)
        return 1;
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}
long long n, g, z, total, p[5] = { 0, 2, 3, 4679, 35617 }, q[5];
const long long mod = 999911658;
long long calculate() {
    long long prod = mod, ans = 0;
    for (int i = 1; i <= 4; i++) {
        long long m = prod / p[i];
        long long v = reverse(m, p[i]);
        ans = (ans + q[i] * m * v) % prod;
    }
    return ans;
}
void divide(long long n) {
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            for (int j = 1; j <= 4; j++) {
                q[j] = (q[j] + Lucas(n, i, p[j])) % p[j];
            }
            if (i * i != n) {
                for (int j = 1; j <= 4; j++) {
                    q[j] = (q[j] + Lucas(n, n / i, p[j])) % p[j];
                }
            }
        }
    }
}
int main() {
    cin >> n >> g;
    g %= mod + 1;
    if (g == 0) {
        exit(puts("0"));
    }
    divide(n);
    long long z = (calculate() + mod) % mod;
    cout << f(g, z, mod + 1) << endl;
    return 0;
}