求大佬看看，实在调不动

卢卡斯是板子，能过数据加强的板子题，可以确保的卢卡斯是对的，应该是别的地方错了

有大佬能给个点1的数据也行

#include<bits/stdc++.h>
#define N 10000005
#define ll long long
#define f(i,n,m) for(register ll i=n;i<=m;i++)
#define mod 999911658
using namespace std;
ll n,g,p,tot,val,mi;
ll fact[N],phi[N],pi[5]={0,2,3,4679,35617};
inline ll qpow(ll a,ll b,ll p){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
inline ll mod_fact(ll n,ll &e){
	e=0;
	if(n<p)return fact[n];
	ll ans=mod_fact(n/p,e);
	e+=n/p;
	return n/p&1? (p-fact[n%p])*ans:fact[n%p]*ans;
}
inline ll lucas(ll n,ll m){
	if(m>n)return 0;
	ll e1,e2,e3;
	ll a1=mod_fact(n,e1),a2=mod_fact(n-m,e2),a3=mod_fact(m,e3);
	if(e1>e2+e3)return 0;
	return a1*qpow(a2*a3%p,p-2,p)%p;
}
inline void crt(){
	ll ta=0;
	fact[0]=1;
	f(i,1,p)fact[i]=fact[i-1]*i%p;
	f(i,1,tot)
	ta=(lucas(n,phi[i])+ta)%p;
	ll mi=mod/p;
	val=(val+ta%mod*mi%mod*qpow(mi,p-2,p))%mod;
}
signed main(){
	scanf("%lld%lld",&n,&g);
	if(g%(mod+1)==0){
		printf("0\n");
		return 0;
	}
    ll k=sqrt(n);
	f(i,1,k){
		if(n%i==0){
			phi[++tot]=i;
			if(i!=k)phi[++tot]=n/i;
			}
	}
	f(i,1,4)p=pi[i],crt();
	printf("%lld\n",qpow(g,val,mod+1));
	return 0;
}