#include<iostream>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
const int mod=999911659;
int fact[100005];
int n,g,p,a[105]={0,2,3,4679,35617},b[105];
int fast_pow(int x,int y,int m)
{
	int ret=1;
	while(y)
	{
		if(y&1) ret=ret*x%m;
		x=x*x%m;
		y>>=1;
	}
	return ret;
}
int C(int x,int y,int m)
{
	if(x>y) return 0;
	return fact[y]*fast_pow(fact[x]*fact[y-x]%m,m-2,m)%m;
}
int Lucas(int x,int y,int m)
{
	if(x==0) return 1;
	return ((Lucas(x/m,y/m,m)%m)*(C(x%m,y%m,m)%m))%m;
}
int CRT(int x,int m)
{
	int ret=0;
	for(int i=1;i<=x;i++)
	{
		int y=m/a[i];
		ret+=(((y*fast_pow(y,a[i]-2,m)%m)*b[i])%m);
	}
	return ret;
}
void get_fact(int x)
{
	fact[0]=1;
	for(int i=1;i<=x;i++) fact[i]=(fact[i-1]*i)%x;
}
int get_ans(int x,int y)
{
	for(int i=1;i<=4;i++)
	{
		get_fact(a[i]);
	    b[i]=Lucas(x,y,a[i]);
	}
	return CRT(4,mod-1);
}
signed main()
{
	scanf("%lld%lld",&n,&g);
	for(int i=1;i<=ceil(sqrt(n));i++)
	{
		if(n%i==0)
		{
			p+=get_ans(i,n);
			if(i<n/i) p+=get_ans(n/i,n);
			p%=(mod-1);
		}
	}
	printf("%lld\n",fast_pow(g,p,mod));
	return 0;
}