#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=999911659;
const ll mod1=2;
const ll mod2=3;
const ll mod3=4679;
const ll mod4=35617;
ll n,g,ans,jc1[5],jc2[5],jc3[4700],jc4[35700],X,Y;
int s;
ll gcd(ll a,ll b){
	return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;
		y=0;
	}else{
		exgcd(b,a%b,x,y);
		x-=a/b*y;
		swap(x,y);
	}
}
ll q_pow(ll a,ll b,ll mod){
	ll ans=1;
	while(b>0){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll C(ll n,ll m,ll mod){
	if(!m) return 1;
	if(n<m) return 0;
	if(n==m) return 1;
	if(mod==mod1) return jc1[n]*q_pow(jc1[m],mod1-2,mod1)%mod1*q_pow(jc1[n-m],mod1-2,mod1)%mod1;
	if(mod==mod2) return jc2[n]*q_pow(jc2[m],mod2-2,mod2)%mod2*q_pow(jc2[n-m],mod2-2,mod2)%mod2;
	if(mod==mod3) return jc3[n]*q_pow(jc3[m],mod3-2,mod3)%mod3*q_pow(jc3[n-m],mod3-2,mod3)%mod3;
	if(mod==mod4) return jc4[n]*q_pow(jc4[m],mod4-2,mod4)%mod4*q_pow(jc4[n-m],mod4-2,mod4)%mod4;
}
ll Lucas(ll n,ll m,ll mod){
	if(!m) return 1;
	if(n<m) return 0;
	if(n==m) return 1;
	return Lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}
ll solve(ll x){
//	printf("x=%lld\n",x);
	ll a1=Lucas(n,x,mod1),a2=Lucas(n,x,mod2),a3=Lucas(n,x,mod3),a4=Lucas(n,x,mod4);
	ll M=mod1*mod2*mod3*mod4,L=lcm(lcm(lcm(mod1,mod2),mod3),mod4);
	ll M1=M/mod1,M2=M/mod2,M3=M/mod3,M4=M/mod4;
	ll ans=0;
	exgcd(M1,mod1,X,Y);
//	printf("X1=%lld\n",X);
	X=(X%mod1+mod1)%mod1;
	ans=(ans+X*M1%L*a1%L)%L;
	exgcd(M2,mod2,X,Y);
//	printf("X2=%lld\n",X);
	X=(X%mod2+mod2)%mod2;
	ans=(ans+X*M2%L*a2%L)%L;
	exgcd(M3,mod3,X,Y);
//	printf("X3=%lld\n",X);
	X=(X%mod3+mod3)%mod3;
	ans=(ans+X*M3%L*a3%L)%L;
	exgcd(M4,mod4,X,Y);
//	printf("X4=%lld\n",X);
	X=(X%mod4+mod4)%mod4;
	ans=(ans+X*M4%L*a4%L)%L;
//	printf("ans=%lld\n",ans);
//	printf("a1=%lld\n",a1);
//	printf("a2=%lld\n",a2);
//	printf("a3=%lld\n",a3);
//	printf("a4=%lld\n",a4);
//	printf("M1=%lld\n",M1);
//	printf("M2=%lld\n",M2);
//	printf("M3=%lld\n",M3);
//	printf("M4=%lld\n",M4);
//	printf("M=%lld\n",M);
//	printf("L=%lld\n",L);
	return ans;
}
int main(){
	jc1[0]=1;
	for(int i=1;i<=mod1;i++) jc1[i]=jc1[i-1]*i%mod1;
	jc2[0]=1;
	for(int i=1;i<=mod2;i++) jc2[i]=jc2[i-1]*i%mod2;
	jc3[0]=1;
	for(int i=1;i<=mod3;i++) jc3[i]=jc3[i-1]*i%mod3;
	jc4[0]=1;
	for(int i=1;i<=mod4;i++) jc4[i]=jc4[i-1]*i%mod4;
	scanf("%lld%lld",&n,&g);
	if(g==0){
		printf("0\n");
		return 0;
	}
	s=sqrt(n);
	for(int i=1;i<=s;i++)
		if(n%i==0){
			ans+=solve(i);
			if(i*i!=n) ans=(ans+solve(n/i))%(mod-1);
		}
	printf("%lld\n",q_pow(g,ans,mod));
	return 0;
}