好吧我数学差的好像不是一点半点……
题目求的是$G^{\sum_{d|n}C^d_n}mod\ 999911659$
我们可以利用费马小定理$a^{k}\equiv a^{k\ mod\ (p-1)}(mod\ p)$
然后组合数可以直接用Lucas搞
那么就做完啦
然而$p-1$并不是质数orz，费马小定理不能用
那么我们考虑把$p-1$分解质数，$999911658=2*3*4679*35617$
我们先用Lucas定理分别算出对这四个数取模的答案，然后得到四个线性同余方程
然后直接用中国剩余定理解出答案就好了（然而我并不会中国剩余定理orz）
//minamoto
#include<cstdio>
#define ll long long
using namespace std;
const int mod=;
ll n,G,val,fac[],a[],b[]={,,,};
inline ll ksm(ll x,ll y,ll p){
ll res=;
while(y){
if(y&) res=res*x%p;
x=x*x%p,y>>=;
}
return res;
}
inline void init(ll p){
fac[]=;
for(int i=;i<=p;++i)
fac[i]=fac[i-]*i%p;
}
inline ll C(ll n,ll m,ll p){
if(n<m) return ;
return fac[n]*ksm(fac[m],p-,p)%p*ksm(fac[n-m],p-,p)%p;
}
ll Lucas(ll n,ll m,ll p){
if(n<m) return ;if(!n) return ;
return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
inline void CRT(){
for(int i=;i<;++i)
val=(val+a[i]*(mod/b[i])%mod*ksm(mod/b[i],b[i]-,b[i]))%mod;
}
int main(){
scanf("%lld%lld",&n,&G);
if(G%(mod+)==) return puts(""),;
for(int k=;k<;++k){
init(b[k]);
for(ll i=;i*i<=n;++i)
if(n%i==){
a[k]=(a[k]+Lucas(n,i,b[k]))%b[k];
if(i*i!=n) a[k]=(a[k]+Lucas(n,n/i,b[k]))%b[k];
}
}
CRT();
printf("%lld\n",ksm(G,val,mod+));
return ;
}