#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=999911658;
const int N=1e5+5;
int n,g,jie[N];
struct node{int a,p;}e[5];
int b[5]={0,2,3,4679,35617};
void init(int p){
	jie[0]=1;
	for(int i=1;i<=p;i++){
		jie[i]=jie[i-1]*i%p;
	}
}
int qpow(int a,int b,int p){
	int ans=1;
	while(b){
		if(b%2)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
int c(int n,int m,int p){
	if(n<m)return 0;
	return jie[n]*qpow(jie[n-m],p-2,p)%p*qpow(jie[m],p-2,p)%p;
}
int lucas(int n,int m,int p){
	if(n<m)return 0;
	if(!n)return 1;
	return lucas(n/p,m/p,p)*c(n%p,m%p,p)%p;
}
int gcd,lcm,x,y;
void exgcd(int a,int b){
	if(b==0){
		gcd=a,x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int o=x;
	x=y;
	y=o-a/b*y;
}
node excrt(node o1,node o2){
    int a1=o1.a,a2=o2.a,p1=o1.p,p2=o2.p,x0;
    exgcd(p1,p2);
    //cout<<x<<endl;
    int o=a2-a1;
    //if(o<0)o=-o;
    assert(o%gcd==0);
    int c=o/gcd;
    lcm=p1*p2/gcd;
    x0=(x*p1*c+a1)%lcm;
    if(x0<0)x0+=lcm;
    return node{x0,lcm};
}
signed main(){
	cin>>n>>g;
	if(g%(mod+1)==0){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=4;i++){
		e[i].p=b[i];
		init(b[i]);
		for(int j=1;j*j<=n;j++){
			if(n%j==0){
				e[i].a=(e[i].a+lucas(n,j,b[i]))%b[i];
			}
			if(j*j!=n){
				e[i].a=(e[i].a+lucas(n,n/j,b[i]))%b[i];
			}
		}
	}
	node ans=excrt(e[1],e[2]);
	for(int i=3;i<=4;i++){
		ans=excrt(ans,e[i]);
	}
	cout<<qpow(g,ans.a,mod+1);
	return 0;
}