mx80分求助

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int L = 999911658;
ll n,g;
ll ysh[50005],tot;
ll fac[50005][5],com[5],Pow;
ll a[5]={0,2,3,4679,35617};

void Exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1,y=0; return;
	}
	Exgcd(b,a%b,x,y);
	ll t=x; x=y,y=t-(a/b)*y;
}
ll ksm(ll x,ll k,ll p){
	ll res=1;
	while(k){
		if(k&1) res=res*x%p;
		x=x*x%p,k>>=1;
	} return res;
}
ll C(ll n,ll m,ll i){
	if(n<m) return 0;
	return fac[n][i]*ksm(fac[m][i],a[i]-2,a[i])%a[i]*ksm(fac[n-m][i],a[i]-2,a[i])%a[i];
}
ll lucas(ll n,ll m,ll i){
	if(m==0) return 1;
	return C(n%a[i],m%a[i],i)*lucas(n/a[i],m/a[i],i)%a[i];
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>g;
    if(g==L+1){
        cout<<0; return 0;
    }
	fac[0][1]=fac[0][2]=fac[0][3]=fac[0][4]=1;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=35617;j++) fac[j][i]=fac[j-1][i]*j%a[i];
	for(int i=1;i*i<n;i++){
		if(n%i==0){
			ysh[++tot]=i;
			ysh[++tot]=n/i;
		}
	}
	if(sqrt(n)*sqrt(n)==n) ysh[++tot]=sqrt(n);
	for(int i=1;i<=4;i++)
		for(int j=1;j<=tot;j++)
			com[i]=(com[i]+lucas(n,ysh[j],i))%a[i];
	for(int i=1;i<=4;i++){
		ll m=L/a[i],x,y;
		Exgcd(m,a[i],x,y);
		x=(x%a[i]+a[i])%a[i];
		Pow=(Pow+m*x%L*com[i]%L)%L;
	}
	cout<<ksm(g,Pow,L+1);
	return 0;
}