#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e7+100;
ll a,b,mod=9901;
ll p[N],cnt,c[N],ans=1;
void f()
{
	ll n=a;
	for(int i=2;i<=n;i++)
	{
		if(n%i) continue;
		p[++cnt]=i;
		int tol=0;
		while(n%i==0) {tol++;n/=i;}
		c[cnt]=tol;
	}
	if(n>1) {p[++cnt]=n;c[cnt]=1;}
	for(int i=1;i<=cnt;i++)
	c[i]=c[i]*b;
}
ll y(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b%2) ans=ans*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ans;
}
ll r()
{
	for(int i=1;i<=cnt;i++)
	{
		if(p[i]>mod&&p[i]%mod==1)
		{
			ans=(c[i]+1)*ans%mod;
			continue;
		}
		ans=ans*(y(p[i],c[i]+1)-1)%mod;
		ans=ans*y(p[i]-1,mod-2)%mod;
	}
} 
int main()
{
	cin>>a>>b;
	f();
	r();
	cout<<(ans%mod+mod)%mod;
	return 0;
}