#include <cstdio>
#define LL long long LL finmo=;
LL fac[][],inv[][];
LL tmp[],rev[];
LL n,g,x,y;
const LL mo[]={,,,}; LL qpow(LL bas,LL pow,LL mo){
LL ret=;
for (;pow;bas*=bas,bas%=mo,pow=pow>>){
if (pow&) ret*=bas,ret%=mo;
}
return(ret);
}//快速幂 LL C(LL t1,LL t2,LL mopo){
if (t2>t1) return();
return((fac[mopo][t1]*inv[mopo][t2])%mo[mopo]*inv[mopo][t1-t2]%mo[mopo]);
}//组合数 LL lucas(int t1,int t2,int mopo){
LL ret=;
while(t1||t2){
ret*=C(t1%mo[mopo],t2%mo[mopo],mopo);ret%=mo[mopo];
t1/=mo[mopo];t2/=mo[mopo];
}
return(ret);
}//lucas定理 LL solve(LL num){
for (int i=;i<=;i++) tmp[i]=lucas(n,num,i);
LL ret=;
for (int i=;i<=;i++)
ret+=tmp[i]*(finmo/mo[i])*rev[i],ret%=finmo-;
return(ret);
}//线性同余方程的解 void exgcd(LL a,LL b,LL &x,LL &y){
if (b==){
x=1LL;y=0LL;return;
}
exgcd(b,a%b,x,y);
LL t=x;x=y;y=t-(a/b)*y;
}//扩展欧几里得 int main(){
scanf("%lld%lld",&n,&g);
for (int i=;i<=;i++){
fac[i][]=;inv[i][]=;
for (int j=;j<mo[i];j++) {fac[i][j]=(fac[i][j-]*j)%mo[i];inv[i][j]=qpow(fac[i][j],mo[i]-,mo[i]);}
}
for (int i=;i<=;i++){
exgcd(finmo/mo[i],mo[i],x,y);
rev[i]=(x%mo[i]+mo[i])%mo[i];
} LL ans=;
for (int i=;i*i<=n;i++)
if (n%i==){
ans+=solve(i);ans%=finmo-;
if (n/i!=i) ans+=solve(n/i),ans%=finmo-;
} LL finans=qpow(g,ans,finmo);
if (g==)printf("0\n");else printf("%lld\n",finans);
}