#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int a=1,b=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while('0'<=ch&&ch<='9') b=b*10+ch-'0',ch=getchar();
	return b;
}
const int p=9901;
int s[65],cnt,ss[65],ct,ans=1;
int qpow(int a,int b){
	int anss=1;
	while(b){
		if(b&1) anss=anss*a%p;
		a=a*a%p;
		b>>=1;
	}
	return anss%p;
}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;y=0;return a;
	}
	int r=exgcd(b,a%b,x,y);
	int tem=x;
	x=y;
	y=tem-a/b*y;
	return r;//
}
int niyuan_tongyu(int a){
	int x,y;
	int d=exgcd(a,p,x,y);
	//if(d!=1) return -1;//无解
	return (x%p+p)%p;
}
int calc(int a,int b){
	if(a%p==1) return b+1;
	else {
		//printf("%lld\n",pow(a,b+1)-1);
		return ((qpow(a,b+1)-1)%p*niyuan_tongyu(a-1)%p)%p;
	}
}
signed main()
{
	int a,b,k=1;
	a=read();b=read();
	//if(a==0) {cout<<0<<endl;return 0;}//特判 
    //if(b==0||a==1) {cout<<1<<endl;return 0;}
	for(int i=2;i<=a-1;i++){
		if(a/i==a*1.0/i) {s[++cnt]=i,ss[cnt]=1;
		k=a/i;
		while(k){
		if(k/i==k*1.0/i) ss[cnt]++,k/=i;
		else break;}
		a=k;
		}
	}
	if(a!=1) {s[++cnt]=a;ss[cnt]=1;}
	//printf("%lld %lld\n",s[i],ss[i]);
	for(int i=1;i<=cnt;i++){
		ss[i]*=b;
	}
	for(int i=1;i<=cnt;i++){
		ans=(ans%p*calc(s[i],ss[i])%p)%p;
	}
	printf("%lld",ans%p);
	return 0;
}