每个部分都检查过了，还是过不了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const long long mod = 999911659;
template <class T>
inline void read(T &x)
{
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
}
const int N = 5e4 + 4;
LL fact[N], factor[N];
int cnt;
inline void exgcd(LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    LL z = x;
    x = y;
    y = z - y * (a / b);
}
inline void init(LL x)
{
    fact[0] = 1;
    for (int i = 1; i <= x; i++)
        fact[i] = (fact[i - 1] * i) % x;
    return;
}
inline void get_factor(LL n)
{
    for (int i = 1; i * i <= n; i++)
        if (n % i == 0)
        {
            factor[++cnt] = i;
            if (n / i != i)
                factor[++cnt] = n / i;
        }
    return;
}
inline LL qpow(LL a, LL b, LL p)
{
    LL res = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = (res * a) % p;
        a = (a * a) % p;
    }
    return res;
}
inline LL com(LL a, LL b, LL p)
{
    if (a < b || b == 0)
        return 0;
    if (b == a)
        return 1;
    return (fact[a] * qpow(fact[a - b], p - 2, p) % p) * qpow(fact[b], p - 2, p) % p;
}
inline LL lucas(LL a, LL b, LL p)
{
    if (a < b)
        return 0;
    if (a == 0)
        return 1;
    return lucas(a / p, b / p, p) * com(a % p, b % p, p) % p;
}
LL m[] = {2, 3, 4679, 35617}, a[5], M[5], n, q;
int main()
{
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    read(n);
    read(q);
    get_factor(n);
    for (int i = 0; i < 4; i++)
    {
        init(m[i]);
        for (int j = 1; j <= cnt; j++)
            a[i] = (a[i] + lucas(n, factor[j], m[i])) % m[i];
    }
    LL ans = 0;
    for (int i = 0; i < 4; i++)
    {
        M[i] = (mod - 1) / m[i];
        LL x = 0, y = 0;
        exgcd(M[i], m[i], x, y);
        if (x < 0)
            x += m[i];
        ans += x * M[i] * a[i];
    }
    printf("%lld", qpow(q, ans % (mod - 1), mod));
    return 0;
}