rt.

本地能输出，交上去显示全部是 $0$，已经改的快跟题解一样了。。

#include <bits/stdc++.h>
using namespace std;

long long read()
{
    long long s = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * w;
}

const int N = 5e4 + 10,mod = 999911658;
long long q[N],r[N],x[N],b[5];
long long T,n,m,g,f[N];
long long multiple = 1,ans;

void init(long long x)
{
    f[0] = 1;
    for(int i = 1;i <= N;i++) f[i] = (f[i - 1] * i) % x;
}

long long exgcd(long long a,long long b,long long &x,long long &y)
{
    long long t;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        t = exgcd(b,a % b,x,y);
        int xx = x;
        x = y;
        y = xx - a / b * y;
        return t;
    }
}

long long quickpow(long long c,long long n,long long m)
{
	long long res = 1;
	while(n)
	{
		if(n & 1) res = res * c % m;
		c = c * c % m;
		n >>= 1;
	}	
	return res;
}

long long C(long long n,long long m,long long p)
{
    if(m > n)return 0;
    return((f[n] * quickpow(f[m],p - 2,p)) % p * quickpow(f[n - m],p - 2,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;
}

int a[5] = {0,2,3,4679,35617};

long long CRT()
{
    for(int i = 1;i <= 4;i++)
    {
        q[i] = a[i];
        multiple = multiple * a[i];
    }
    for(int i = 1;i <= 4;i++)
    {
        r[i] = multiple / q[i];
        long long x = 0,y = 0;
        exgcd(r[i],q[i],x,y);
        if (x < 0) ans += b[i] * r[i] * (x + q[i]);
        else ans += b[i] * r[i] * x;
    }
    return ans % multiple;
}

int main()
{
    //freopen("input.in","r",stdin);
    n = read(),g = read();
    if(g % 999911659 == 0){cout << 0 << endl;return 0;}
    for(int i = 1;i <= 4;i++)
    {
        init(a[i]);
        for(int j = 1;j * j <= n;j++)
        {
            if(n % j == 0)
            {
                b[i] = (b[i] + Lucas(n,j,a[i])) % a[i];
				if(j * j == n) continue;
				b[i] = (b[i] + Lucas(n,n / j,a[i])) % a[i];
            }
        }
    }
    cout << quickpow(g,CRT(),mod) << endl;
    return 0;
}