#include<cstdio>
typedef long long ll;
using namespace std;
const int N=1e5+10;
const ll mod=999911659;
struct rr{
	ll l(){
		ll res=0,l=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-')l=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
		return res*l;
	}
	int i(){
		int res=0,l=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-')l=-1;
		c=getchar();
		}
		while(c>='0'&&c<='9'){
			res=res*10+c-'0';
			c=getchar();
		}
		return res*l;
	}
}read;
struct ms{
	ll exgcd(ll a,ll b,ll &x,ll &y){
		if(!b){
			x=1,y=0;return a;
		}
		ll d=exgcd(b,a%b,x,y);
		ll z=x;x=y;y=z-(a/b)*y;
		return d;
	}
	ll CRT(ll m[],ll a[],ll k){
		ll M=1,ans=0;
		for(int i=1;i<=k;++i)M*=m[i];
		for(int i=1;i<=k;++i){
			ll x,y;
			exgcd(M/m[i],m[i],x,y);
			ans=(ans+(M/m[i])*a[i]*x)%M;
		}
		return (ans+M)%M;
	}
	ll gcd(ll a,ll b){
		if(!b)return a;
		return gcd(b,a%b);
	}
	ll mul(ll a,ll b,ll mod){
		ll ans=0;
		while(b>0){
			if(b&1)ans=(ans+a)%mod;
			a=(a+a)%mod;
			b>>=1;
		}
		return ans;
	}
	ll crt(ll m[],ll a[],ll k){
		ll ans=a[1],M=m[1],x,y;
		for(int i=2;i<=k;++i){
			ll b=m[i];
			ll c=(a[i]-ans%b+b)%b;
			ll d=exgcd(M,b,x,y);
			if(c%d)return -1;
			x=mul(x,c/d,b/d);
			ans+=x*M;
			M=M*(m[i]/d);
			ans=(ans%M+M)%M;
		}
		return ans;
	}
	ll qp(ll a,ll b,ll p){
		ll res=1;
		while(b>0){
			if(b&1)res=res*a%p;
			a=a*a%p;
			b>>=1;
		}
		return res;
	}
	ll inverse(ll a,ll p){
		ll ans,y;
		exgcd(a,p,ans,y);
		return ans;
	}
	ll calc(ll n,ll x,ll P){//递归求解，x表示质因子 
		if(!n)return 1;//边界，类比lucas 返回1 
		ll s=1;
		for(ll i=1;i<=P;i++)if(i%x)s=s*i%P;//x是质因子，不是倍数不互质 
		s=qp(s,n/P,P);
		//这是在求中间项 
		for(ll i=n/P*P+1;i<=n;++i)
			if(i%x)s=i%P*s%P;
		//求左边项，将那些没有算的算一下 
		return s*calc(n/x,x,P)%P;
		//求右边项 
	}
	ll multilucas(ll n,ll m,ll x,ll P){//从n中选m个，x为质因子 
		int cnt=0;
		for(ll i=n;i;i/=x)cnt+=i/x; 
		for(ll i=m;i;i/=x)cnt-=i/x;
		for(ll i=n-m;i;i/=x)cnt-=i/x;
		return qp(x,cnt,P)*calc(n,x,P)%P*inverse(calc(m,x,P),P)%P*inverse(calc(n-m,x,P),P)%P; 
	} 
	ll Q[5];
	void lucas_init(){
		Q[1]=2;Q[2]=3;Q[3]=4679;Q[4]=35617;
	}
	ll exlucas(ll n,ll m,ll P){
		ll a[5],cnt=4;
		for(int i=1;i<=cnt;++i)a[i]=multilucas(n,m,Q[i],Q[i]);
		return CRT(Q,a,cnt);
	}
}MS;
ll n,ans,g;
#include<cmath> 
int main(){
	n=read.l(),g=read.l();
	MS.lucas_init();
	ll k=sqrt(n);
	bool flag;
	if(n/k==k)flag=1;
	else flag=0;
	for(int i=1;i*i<=n;++i){
		if(n%i==0&&i==k&&flag)ans=(ans+MS.exlucas(n,i,mod-1))%(mod-1);
		else if(n%i==0)ans=((ans+MS.exlucas(n,n/i,mod-1))%(mod-1)+MS.exlucas(n,i,mod-1))%(mod-1);
	}
	ans=MS.qp(g,ans,mod);
	printf("%lld\n",ans);
	return 0;
}