/*
古代猪文：Lucas定理+中国剩余定理
999911658=2*3*4679*35617
Lucas定理：(m,n)=(sp,tp)(r,q) %p
中国剩余定理：x=sum{si*Mi*ti}+km
先求出sum{C(d,n)}%p[i]=a[i]
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 999911659
#define maxn 100005
ll m[]={,,,};
ll f[][maxn],a[],d[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==){x=,y=;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;x=y,y=z-a/b*y;
return d;
}
ll inv(ll a,ll Mod){
ll x,y;
exgcd(a,Mod,x,y);
return (x+Mod)%Mod;
}
ll C(int i,ll n,ll k,ll p){return f[i][n]*inv(f[i][k]*f[i][n-k]%p,p)%p;}
ll lucas(int i,ll n,ll k,ll p){
int res=;
while(n&&k){
res=res*C(i,n%p,k%p,p)%p;
if(res==)return ;
n/=p,k/=p;
}
return res;
}
ll Pow(ll x,ll n,ll Mod){
ll res=;
while(n){
if(n%)res=res*x%Mod;
n>>=;x=x*x%Mod;
}
return res;
}
ll china(int n,ll a[],ll m[]){
ll M=,res=;
for(int i=;i<n;i++)M*=m[i];
for(int i=;i<n;i++){
ll w=M/m[i],x,y;
exgcd(w,m[i],x,y);
res=(res+x*w*a[i])%M;
}
return (res+M)%M;
} int main(){
ll n,g;
cin>>n>>g;
if(g==mod){puts("");return ;}
int tot=;
for(int i=;i*i<=n;i++)
if(n%i==){//求n的所有质因子
if(i*i==n)d[tot++]=i;
else d[tot++]=i,d[tot++]=n/i;
}
for(int i=;i<;i++){
f[i][]=;
for(int j=;j<m[i];j++)
f[i][j]=f[i][j-]*j%m[i];
}
for(int i=;i<tot;i++)
for(int j=;j<;j++)
a[j]=(a[j]+lucas(j,n,d[i],m[j]))%m[j];;
ll ans=china(,a,m);
cout<<Pow(g,ans,mod);
}