样例没过交上去100？怪了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int g,nn,sum,ys[10]={0,2,3,4679,35617},b[10];
int qpow(int x,int y,int p){
	 int res=1;
	 while(y){
	 	if(y&1)res=res*x%p;
	 	x=x*x%p;
	 	y>>=1;
	 }
	 return res;
}
int c(int n,int m,int p){
	if(m>n)return 0;
	int a=1,b=1;
	for(int i=n;i>n-m;i--)a=(a%p*(i%p))%p;
	for(int i=1;i<=m;i++)b=(b%p*(i%p))%p;
	return a*qpow(b,p-2,p)%p;
}
int lucas(int n,int m,int p){
    if(m==0)return 1;
    return c(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
void exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y;
}
int CRT(){
    int m=999911658,ans=0;
    for(int i=1;i<5;i++){
        int mi=m/ys[i],x,y;
        exgcd(mi,ys[i],x,y);
        ans=((ans+mi*x*b[i])%m+m)%m;
    }
    return ans;
}
int exlucas(int n,int m){
    for(int i=1;i<5;i++)b[i]=lucas(n,m,ys[i]);
    return CRT();
}
signed main(){
    cin>>nn>>g;
    if(g==999911659){cout<<0;return 0;}
    for(int i=1;i*i<=nn;i++){
        if(i*i==nn){
            sum+=exlucas(nn,i);sum%=999911658;
        }
        if(nn%i==0){
           sum+=exlucas(nn,i)+exlucas(nn,nn/i);sum%=999911658;
        }
    }
    cout<<qpow(g,sum,999911659);
}