#include<cstdio>
#define int long long
#define mod 999911658
int size,worth,frac[35618],data[5],moder[5]={0,2,3,4679,35617};
int power(int first,int second,int moder){
	int result=0;
	while(second){
		if(second&1){
			(result*=first)%=moder;
		};
		(first*=first)%=moder;
		second>>=1;
	};
	return result;
};
inline void remake(int moder){
	frac[0]=1;
	for(int iter=1;iter<=moder;++iter){
		frac[iter]=frac[iter-1]*iter%moder;
	};
	return;
};
inline int partly(int first,int second,int moder){
	if(first<second){
		return 0;
	};
	return frac[first]*power(frac[second],moder-2,moder)%moder*power(frac[first-second],moder-2,moder)%moder;
};
inline int lucas(int first,int second,int moder){
	if(first<second){
		return 0;
	};
	if(first==0){
		return 1;
	};
	return lucas(first/moder,second/moder,moder)*partly(first%moder,second%moder,moder)%moder;
};
inline int crt(void){
	int result=0;
	for(int iter=1;iter<=4;++iter){
		(result+=data[iter]*(mod/moder[iter])*power(mod/moder[iter],moder[iter]-2,moder[iter]))%=mod;
	};
	return result;
};
signed main(signed,char**){
	scanf("%lld %lld",&size,&worth);
	if(worth%(mod+1)==0){
		putchar('0');
		return 0;
	};
	for(int first=1;first<=4;++first){
		remake(moder[first]);
		for(int second=1;second*second<=size;++second){
			if(size%second==0){
				(data[first]+=lucas(size,second,moder[first]))%=moder[first];
				if(second*second!=size){
					(data[first]+=lucas(size,size/second,moder[first]))%=moder[first];
				};
			};;
		};
	};
	printf("%lld",power(worth,crt(),mod+1));
	return 0;
};