#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define int long long
const int N=3e5+100;
const ll mod=999911658;
const ll Mod=999911659;
ll ksm(ll x,ll o){
ll ans=1,res=x%Mod;
while(o){
if(o&1) ans=(ans*res)%Mod;
res=(res*res)%Mod;
o>>=1;
}
return ans%Mod;
}
ll n;
ll g;
ll m[5]={0,2,3,4679,35617},M[5],MM,t[5];
ll d[N],num;
void divide(ll x){
int top=floor(sqrt(x));
d[++num]=1;
for(int i=2;i<=top;i++){
if(x%i==0){
d[++num]=i;
if(n/i!=i) d[++num]=n/i;
}
}
d[++num]=x;
return;
}
ll ni[5][N],jc[N];
ll a[5];
ll C(int k,ll d,ll n){
if(d>n) return 0;
return (jc[n]*ni[k][d]*ni[k][n-d])%m[k];
}
ll lucas(int k,ll d,ll n){
if(d==n) return 1;
if(d>n) return 0;
return (C(k,d%m[k],n%m[k])%m[k])*lucas(k,d/m[k],n/m[k])%m[k];
}
void gcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;return;
}
gcd(b,a%b,x,y);int o=y;
y=x-a/b*y;
x=o;
y%=mod;x%=mod;
}
signed main(){
scanf("%lld%lld",&n,&g);
if(g%Mod==0) {printf("0");return 0;}
divide(n);
jc[0]=jc[1]=1;
for(int i=1;i<=4;i++) ni[i][0]=ni[i][1]=1;
for(int i=2;i<=35167;i++){
jc[i]=(jc[i-1]*i)%mod;
for(int j=1;j<=4;j++) ni[j][i]=((m[j]-m[j]/i)*ni[j][m[j]%i])%m[j];
}
for(int i=2;i<=35167;i++)
for(int j=1;j<=4;j++)
ni[j][i]=(ni[j][i]*ni[j][i-1])%m[j];
for(int i=1;i<=num;i++){
for(int j=1;j<=4;j++){
a[j]=(a[j]+lucas(j,d[i],n))%m[j];
//printf("d=%lld mod=%lld ans=%lld\n",d[i],m[j],lucas(j,d[i],n)%m[j]);
}
}
MM=mod;
ll ans=0;
for(int i=1;i<=4;i++){
M[i]=MM/m[i];
ll o;
gcd(M[i],m[i],t[i],o);
ans+=(t[i]*M[i]*a[i])%mod;
ans%=mod;
}
// for(int j=1;j<=4;j++){
// printf("k=%d mod=%d:\n",j,m[j]){
// for(int i=1;i<=num;i++){
// printf
// }
// }
// }
ans%=MM;
while(ans<0) ans+=MM;
printf("%lld\n",ksm(g,ans)%Mod);
return 0;
}
/*
4
5 1
5 2
7 3
4 2
*/