求助：本地通过，交上去全部显示除0

#include<bits/stdc++.h>
#define mod 999911659
#define ll long long
#define maxn 40004
#define fmod 999911658
using namespace std;
ll n,g;
ll f[5][maxn],invf[5][maxn],pmod[5]={0,2,3,4679,35617};
ll poww(ll x,ll k,ll p){
	if(x%p==0) return 0;
	ll ans=1;
	//cout<<x<<" "<<k<<" "<<p<<endl;
	while(k){
	//	cout<<x<<endl;
		if(k&1) ans=ans*x%p;
		x=x*x%p;
		k>>=1;
	}
	return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y=-(a/b)*x;
	return d;
}
void init(int len,int x){
	ll p=pmod[x];
	f[x][0]=1;
	for(int i=1;i<=p-1;i++){
		f[x][i]=f[x][i-1]*i%p;
	}
	invf[x][p-1]=poww(f[x][p-1],p-2,p);
	for(int i=p-1;i>=1;i--){
		invf[x][i-1]=invf[x][i]*i%p;	
	}
}
ll C(int x,int y,int p,int op){
	if(y>x) return 0;
	return f[op][x]*invf[op][y]%p*invf[op][x-y]%p;
}
ll lucas(ll x,ll y,ll p,int op){
	if(x<p&&y<p){
		return C(x,y,p,op);
	}
	return C(x%p,y%p,p,op)*lucas(x/p,y/p,p,op)%p;
}
ll b[5];
ll cntans(ll x){
	for(int j=1;j<=4;j++){
		b[j]+=lucas(n,x,pmod[j],j);
		if(b[j]>pmod[j]) b[j]-=pmod[j]; 
	}
}
ll work(){
	ll ans=0;
	for(int i=1;i*i<=n;i++){
		if(n%i) continue;
		cntans(i);
		if(i*i!=n){
			cntans(n/i);
		}
	}
	for(int j=1;j<=4;j++){
		ans=(ans+b[j]*(fmod/pmod[j])%fmod*poww(fmod/pmod[j],pmod[j]-2,pmod[j])%fmod)%fmod;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&g);
	for(int i=1;i<=4;i++){
		init(maxn-4,i);
	}
	printf("%lld",poww(g,work(),mod));
	return 0;
}