看题解一样，拆系数$\rm Lucas + CRT$合并，但是莫名其妙输出的极大的数。。。求助QAQ

（$\rm Lucas$中用的是线性递推逆元，$\rm CRT$中的$\rm exgcd$也换成了线性递推逆元）

#include<cstdio>
int n,g;
const int mod=999911659,p[4]={2,3,4679,35617};
int a[4],pow[4][36005],inv[4][36005];
inline void init(){
    for(int j=0;j<4;++j){
        inv[j][0]=inv[j][1]=1;
        pow[j][0]=pow[j][1]=1;
        for(int i=2;i<=p[j];++i){
            pow[j][i]=1ll*pow[j][i-1]*i%p[j];
            inv[j][i]=1ll*(p[j]-p[j]/i)*inv[j][p[j]%i]%p[j];
        }
    }
}
inline int power(int a,int b){
    int ans=1;
    if(!a)return b==1?1:0;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
    return ans;
}
inline int Add(int a,int b,int mod){
    return a+b>=mod?a+b-mod:a+b;
}
inline int C(int n,int m,int id){
    return n>m?0:1ll*pow[id][m]*inv[id][pow[id][n]]%p[id]*inv[id][pow[id][m-n]]%p[id];
}
inline int Lucas(int n,int m,int id){
    return !n?1:1ll*Lucas(n/p[id],m/p[id],id)*C(n%p[id],m%p[id],id)%p[id];
}
inline void GetAns(int n,int m){
    for(int i=0;i<4;++i)a[i]=Add(a[i],Lucas(n,m,i),p[i]);
}
inline int CRT(){
    int i,m,M=mod-1,ans=0;
    for(i=0;i<4;++i){
        m=M/p[i];
        ans=Add(ans,1ll*m*inv[i][m%p[i]]*m%M*a[i]%M,M);
    }
}
inline int Solve(int n){
    int i;
    for(i=1;i*i<=n;++i)if(!(n%i)){
        GetAns(i,n);
        if(i*i!=n)GetAns(n/i,n);
    }
    return CRT();
}
signed main(){
    init();
    scanf("%d%d",&n,&g);
    printf("%d",power(g,Solve(n)));
}