rt，过了样例，中国剩余定理没学，自己用小奥口胡了一个过了板子所以看上去非常非主流（）

// Problem: P2480 [SDOI2010]古代猪文
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2480#submit
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Forever1507

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, g, mod = 999911659;
// 2*3*4679*35617
int fac[10000005], a[1000] = {0, 2, 3, 4679, 35617}, b[1000];
vector<int> p;
void zh() {
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) p.push_back(i);
    }
    return;
}
int qpow(long long a, int b, int p) {
    int ans = 1;
    a = (a % p + p) % p;
    for (; b; b >>= 1) {
        if (b & 1) ans = (a * ans) % p;
        a = (a * a) % p;
    }
    return ans;
}
void work() {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
}
int inv(int x, int p) { return qpow(x, p - 2, p); }
int C(int n, int m, int p) {
    if (n > m) return 0;
    return fac[m] * inv(fac[n], p) % p * inv(fac[m - n], p) % p;
}
int lucas(int k, int m, int p) {
    if (m == 0) return 1;
    return C(k % p, m % p, p) * lucas(k / p, m / p, p) % p;
}
int lcm(int a, int b) { return a / __gcd(a, b) * b; }
signed main() {
    cin >> n >> g;
    zh();
    work();
    int ans = 0;
    for (int i = 0; i < p.size(); ++i) {
        //	cout<<p[i]<<'\n';
        ans = (ans + lucas(p[i], n, mod)) % mod;
    }
    //	cout<<ans<<'\n';
    int maxn = 0, mb = 0;
    for (int i = 1; i <= 4; ++i) {
        b[i] = ans % a[i];
        if (a[i] > maxn) maxn = a[i], mb = b[i];
    }
    int cnt = mb, _ = maxn;
    while (1) {
        bool flag = 0;
        for (int i = 1; i <= 4; ++i)
            if (cnt % a[i] != b[i])
                flag = 1;
            else
                _ = lcm(_, a[i]);
        if (!flag) {
            cout << qpow(g, cnt, mod);
            return 0;
        }
        cnt += _;
    }
    return 0;
}