快速幂+枚举质因数+欧拉定理+lucas定理+CRT。
注意两点：
1.if (n<m） C(n,m)=0.
2.这里0^0时应该return 0.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mod 999911659
#define mod2 999911658
#define maxn 40050
using namespace std;
long long g,n,p[]={,,,,},a[],inv1[maxn],inv2[maxn];
long long f_pow(long long x,long long y,long long mods)
{
x%=mods;
if ((!x) && (!y)) return ;
long long ans=,base=x;
while (y)
{
if (y&) ans=(ans*base)%mods;
base=(base*base)%mods;
y>>=;
}
return ans;
}
void get_table(long long x)
{
inv1[]=inv2[]=;
for (long long i=;i<=p[x]-;i++)
{
inv1[i]=inv1[i-]*i%p[x];
inv2[i]=f_pow(inv1[i],p[x]-,p[x]);
}
}
long long comb(long long n,long long m,long long type)
{
if (n<m) return ;
return inv1[n]*inv2[m]%p[type]*inv2[n-m]%p[type];
}
long long lucas(long long n,long long m,long long type)
{
if (!m) return ;long long ret=comb(n%p[type],m%p[type],type);
return comb(n%p[type],m%p[type],type)*lucas(n/p[type],m/p[type],type)%p[type];
}
long long combines()
{
long long ret=;
for (long long i=;i<=;i++)
ret=(ret+a[i]*(mod2/p[i])%mod2*f_pow(mod2/p[i],p[i]-,p[i])%mod2)%mod2;
return ret;
}
long long ask()
{
for (long long i=;i<=;i++)
{
get_table(i);long long top=(long long)(sqrt(n)+0.5);
for (long long j=;j<=top;j++)
{
if (!(n%j))
{
a[i]=(a[i]+lucas(n,j,i))%p[i];
if (j*j!=n) a[i]=(a[i]+lucas(n,n/j,i))%p[i];
}
}
}
return combines();
}
int main()
{
scanf("%lld%lld",&n,&g);
printf("%lld\n",f_pow(g,ask(),mod));
return ;
}