求出对于 999911658 的每个质因数取模的结果，然后 EXCRT 合并（我不会 CRT）。
咋回事呢？

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
namespace maths{
    template<class T>
    T gcd(T a,T b){
        return !b?a:gcd(b,a%b);
    } 
    template<class T>
    T lcm(T a,T b){
        return a/gcd(a,b)*b;
    }
    template<class T>
    T exgcd(T a,T b,T& x,T& y){
        if(!b){
            x=1;
            y=0;
            return a;
        }
        T _gcd=exgcd(b,a%b,x,y);
        ll tmp=x;
        x=y;
        y=tmp-a/b*y;
        return _gcd;
    }
    template<class T>
    void axbyc(T a,T b,T c,T& x0,T& y0){
        ll _gcd=exgcd(a,b,x0,y0);
        x0*=(c/_gcd);
        y0*=(c/_gcd);
        if(c%_gcd!=0)x0=-1;
    }
    template<class T>
    ll excrt(T& mods,T& rest,int len){
        // 从给定下标开始，前 len 个
        queue<pair<ll,ll> > q;
        FOR(i,0,len-1){
            q.push(mkpr(mods[i],rest[i]));
        }
        while(q.size()>1){
            auto f1=q.front();
            q.pop();
            auto f2=q.front();
            q.pop();
            ll m1=f1.first;
            ll r1=f1.second;
            ll m2=f2.first;
            ll r2=f2.second;
            ll k1,k2;
            axbyc(m1,-m2,r2-r1,k1,k2);
            ll sum=k1*m1+r1;
            q.push(mkpr(lcm(m1,m2),sum%lcm(m1,m2)));
        }
        return q.front().second;
    }
    template<class T>
    T qpow(T a,T b,const T mod){
        T res=1;
       // printf("a = %lld b = %lld\n",a,b);
        while(b){
            if(b&1)res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }        
        return res;
    }
    template<class T>
    T qpow(T a,T b){
        T res=1;
        while(b){
            if(b&1)res=res*a;
            a=a*a;
            b>>=1;
      //      printf("b=  %lld\n",b);
        }        
        return res;
    }
    template<class T>
    T inv(T a,const T mod){
		ll x,y;
		exgcd(a,mod,x,y);
		return (x%mod+mod)%mod; 
    }
    template<class T,const T mod,const int maxn>
    struct Comb_num_prime{
        T fact[maxn+5];
        T factinv[maxn+5];
        void init(){
            fact[0]=1;
            FOR(i,1,maxn-1){
                fact[i]=fact[i-1]*T(i)%mod;
             //   printf("mod = %ll fact[%d] = %lld\n",mod,i,fact[i]);
            }
            factinv[maxn-1]=inv(fact[maxn-1],mod);
            REP(i,maxn-1,0){
                factinv[i-1]=factinv[i]*T(i)%mod;
            }
          //  printf("fact[%d] = %lld\n",maxn,fact[maxn]);
        }
        T C(T n,T m){
            if(n<m)return 0;
            return fact[n]*factinv[m]%mod*factinv[n-m]%mod;
        }
        T lucas(ll n,ll m,ll p){
            if(n<m)return 0;
            if(n==0)return 1;
            return lucas(n/p,m/p,p)*C(n%p,m%p)%p;
        }
    };
    template<class T>
    struct Comb_num_notprime{
        T fac(T n,T p,T pk){
            // 1,2,3,...,n 中所有与 p 互质的数乘积，对 p^k 取余
            if(!n){
                return 1;
            }
            T ans=1;
            for(T i=1;i<pk;i++){
                if(i%p){
                    ans=ans*i%pk;
                }
            }
            ans=qpow(ans,n/pk,pk);
            for(T i=1;i<=n%pk;i++){
                if(i%p){
                    ans=ans*i%pk;
                }
            }
            return ans*fac(n/p,p,pk)%pk;
        }
        T C(T n,T m,T p,T k){
            if(n<m)return 0;
          //  printf("%lld %lld %lld %lld\n",n,m,p,k);
            T pk=qpow(p,k);
            ll fn=fac(n,p,pk);
            ll fm=fac(m,p,pk);
            ll fnjm=fac(n-m,p,pk);
        //    printf("fn = %lld fm  = %lld fnjm =  %lld\n",fn,fm,fnjm);
           // puts("???");
            ll cnt=0;
            for(ll i=n;i;i/=p){
            	cnt+=i/p;
			}
			for(ll i=m;i;i/=p){
				cnt-=i/p;
			}
			for(ll i=n-m;i;i/=p){
				cnt-=i/p;
			}
            //puts("???2");
       //     printf("pk = %lld cnt = %lld\n",pk,cnt);
            ll ans=fn*inv(fm,pk)%pk*inv(fnjm,pk)%pk;
          //  printf("pans = %lld\n",ans);
         //   printf("p = %lld pk = %lld\n",p,pk);
            //printf("final = %lld tmp = %lld\n",ans,qpow(p,-cnt,pk)); 
			ans*=qpow(p,cnt,pk)%pk;
			ans%=pk;
			//printf("final = %lld\n",ans); 
			return ans;
        }
		vector<tuple<T,T,T> > static_mods;// (mod,k,mod^k)
        T exlucas(T n,T m,T p){
			if(static_mods.empty()){
                #define BRUTE
				#ifdef BRUTE
				T tmp=p;
				for(T i=2;i*i<=tmp;i++){
					if(tmp%i==0){
						T cnt=0;
						while(tmp%i==0){
							tmp/=i;
							cnt++;
						}
						static_mods.emplace_back(make_tuple(i,cnt,qpow(i,cnt)));
					}
				}
				if(tmp>1){
					static_mods.emplace_back(make_tuple(tmp,1,tmp));
				}
				#endif
                #ifndef BRUTE
				static_mods={{2,1,2},{3,1,3},{4679,1,4679},{35617,1,35617}};
                #endif
			}
            vector<T> mods,rest;
            for(auto& [p,k,pk]:static_mods){
			//	printf("%lld %lld %lld\n",p,k,pk);
				mods.emplace_back(pk);
				rest.emplace_back(C(n,m,p,k));
			}
            return excrt(mods,rest,(int)mods.size());
        }
    };
}
const ll mod=999911659;
ll mods[4]={2,3,4679,35617};
ll rest[4];
int main()
{
	ll n,g;
    scanf("%lld%lld",&n,&g);
    if(mod%g==0){
        puts("0");
        return 0;
    }
    maths::Comb_num_prime<ll,2,2> func0;
    maths::Comb_num_prime<ll,3,3> func1;
    maths::Comb_num_prime<ll,4679,4679> func2;
    maths::Comb_num_prime<ll,35617,35617> func3;
    func0.init();
    func1.init();
    func2.init();
    func3.init();
    for(int d=1;d*d<=n;d++){
        if(n%d==0){
            rest[0]+=func0.lucas(n,d,2);
            if(n/d!=d){
                rest[0]+=func0.lucas(n,n/d,2);
            }
            rest[0]%=2;
        }
    }
    for(int d=1;d*d<=n;d++){
        if(n%d==0){
            rest[1]+=func1.lucas(n,d,3);
            if(n/d!=d){
                rest[1]+=func1.lucas(n,n/d,3);
            }
            rest[1]%=3;
        }
    }
    for(int d=1;d*d<=n;d++){
        if(n%d==0){
            rest[2]+=func2.lucas(n,d,4679);
            if(n/d!=d){
                rest[2]+=func2.lucas(n,n/d,4679);
            }
            rest[2]%=4679;
        }
    }
    for(int d=1;d*d<=n;d++){
        if(n%d==0){
            rest[3]+=func3.lucas(n,d,35617);
        //    printf("d = %lld += %lld\n\n",d,func3.lucas(n,d,35617));
            if(n/d!=d){
                rest[3]+=func3.lucas(n,n/d,35617);
            }
            rest[3]%=35617;
        }
    }
    ll combsum=maths::excrt(mods,rest,4);
	printf("%lld\n",maths::qpow(g,combsum,mod));
    return 0;
}