/*****************************************
备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
const int mod = 999911659;
LL num[N],len , n1[5] , inv[5];
LL cc[5] = {0,2,3,4679,35617};
LL power(LL a, LL b ,LL m)
{
	LL ans = 1;
	while(b)
	{
		if(b&1)
			ans = (ans * a) % m;
		b >>= 1;
		a = (a*a)%m;
	}
	return ans;
}
LL C(LL n , LL m , LL p)
{
	if(n < m)
		return 0;
	if(m < n-m)
		m = n-m;
	LL ans ,sum;
	ans = sum = 1;
	for(int i = 0 ; i < m ; i++)
	{
		ans = (ans * (n-i))%p;
		sum = (sum * (i+1))%p;
	}
	return (ans * power(sum , p-2 , p) ) %p;
}
LL lucas(LL n , LL m , LL p)
{
	if(!m) return 1;
	return (lucas(n/p , m/p , p) * C(n%p , m%p , p) )%p;
}
LL k[N];
LL CRT()
{
	LL sums = 0;
	for(int i = 1; i <= 4 ;i++)
		sums = (sums + ((k[i]*n1[i])%(mod-1))*inv[i])%(mod-1);
	return sums;
}
void init(LL n)
{
	for(int i = 1 ; i *i < n ; i++)
		if(n%i == 0)
			num[len++] = i , num[len++] = n/i;
	LL p = sqrt(n);
	if(p*p == n)
		num[len++] = p;
	LL nums = mod - 1;
	for(int i = 1 ;i <= 4; i++)
	{
		n1[i] = nums/cc[i];
		inv[i] = power(n1[i] , cc[i]-2 , cc[i]);
	}
}
int main()
{
	LL n,q;
	cin >> n >> q;
	if(q%mod == 0)
	{
		cout << 0;
		return 0;
	}
	init(n);
	LL sum = 0;
	for(int j = 1 ;j <= 4 ;j++)
		for(int i = 0 ; i < len ; i++)
			k[j] += lucas(n,num[i],cc[j]);
	sum = CRT();
	cout << power(q,sum,mod);
	return 0;
}

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
//999911658=2*3*4679*35617
#define LL long long
#define mod 999911659
using namespace std;
LL N,G,e;
LL x[4];
LL pre[4][40000];
LL ni[4][40000];
LL zs[4]={2,3,4679,35617};
LL gcd(LL a,LL b,LL &x,LL &y)//求逆元
{
    if(b==0) {x=1;y=0;}
    else     {gcd(b,a%b,y,x); y-=(a/b)*x;}
}
LL lucas(LL p,LL q,LL o)//卢卡斯定理
{
    LL sum=1;
    while(p && q)
    {
        LL x=p%zs[o],y=q%zs[o];
        if(y>x) return 0;
        sum=(sum*(pre[o][x]*(ni[o][x-y]*ni[o][y])%zs[o])%zs[o])%zs[o];
        p/=zs[o];
        q/=zs[o];
    }
    return sum;
}
int main()
{
    scanf("%lld%lld",&N,&G);
    if(G%mod==0) {printf("0\n");return 0;}
    for(int o=0;o<4;o++)//预处理
    {
        pre[o][0]=1;ni[o][0]=1; 
        for(int i=1;i<=zs[o];i++)
        pre[o][i]=(pre[o][i-1]*i)%zs[o];
        ni[o][zs[o]-1]=zs[o]-1;
        for(int i=zs[o]-2;i>=1;i--)
        ni[o][i]=(ni[o][i+1]*(i+1))%zs[o];
        for(LL i=1;i<=sqrt(N);i++)//统计组合数
        if(N%i==0)
        {
            x[o]=(x[o]+lucas(N,i,o))%zs[o];
            if(i*i<N) x[o]=(x[o]+lucas(N,N/i,o))%zs[o];
        }
    };
    for(int i=0;i<4;i++)//中国剩余定理
    {
        LL o,p;
        LL M=(mod-1)/zs[i];
        gcd(M,zs[i],o,p);
        e=(e+x[i]*o*M)%(mod-1);
    }
    while(e<=0) e+=mod-1;
    LL ans=1,a=G;
    while(e)
    {
        if(e&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        e>>=1;
    }
    printf("%lld\n",ans);
    return 0;
}