特判过了，挂的是#11不是#13

Wrong Answer.wrong answer On line 1 column 1, read 4, expected 2.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int P=4e4,mod=999911659;
const int m[5]={mod-1,2,3,4679,35617};
int fact[P],inv[P],d[600],a[5],tot=0;
int qpow(int a,int b,int p)
{
	int res=1;
	a%=p;
	while(b)
	{
		if(b&1)res=res*a%p;
		a=a*a%p,b>>=1;
	}
	return res;
}
void init(int p)
{
	fact[0]=1;
	for(int i=1;i<=p;i++)fact[i]=fact[i-1]*i%p;
	inv[0]=inv[1]=1;
	for(int i=2;i<p;i++)inv[i]=(p-p/i)*inv[p%i]%p;
	return;
}
int C(int n,int m,int p)
{
	if(n<m)return 0;
	return fact[n]*inv[fact[n-m]]%p*inv[fact[m]]%p;
}
int Lucas(int n,int m,int p)
{
	if(m==0)return 1;
	return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
void solve(int n,int x)
{
	init(m[x]);
	for(int i=1;i<=tot;i++)a[x]=(a[x]+Lucas(n,d[i],m[x]))%m[x];
	return;
}
int CRT()
{
	int res=0;
	for(int i=1;i<=4;i++)
	{
		int M=m[0]/m[i];
		res=(res+a[i]*M*qpow(M,m[i]-2,m[i]))%m[0];
	}
	return res;
}
signed main()
{
	int n,g;
	scanf("%lld %lld",&n,&g);
	if(g==mod)return printf("0")&0;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i!=0)continue;
		d[++tot]=i;
		if(n/i!=i)d[++tot]=n/i;
	}
	for(int i=1;i<=4;i++)solve(n,i);
	printf("%lld",qpow(g,CRT(),mod));
	return 0;
}