#include<cstdio>

const int R=9901;
const int N=150000;

int a,b,nr,pr[N],exp[N],s=1;

void citire()
{
	freopen("sumdiv.in","r",stdin);
	freopen("sumdiv.out","w",stdout);
	scanf("%d%d",&a,&b);
}

void desc(int x)
{
	int p;
	for (int i=2;i*i<=x;++i)
		if (x%i==0)
		{
			p=0;
			for (;x%i==0;++p,x/=i);
			pr[++nr]=i;
			exp[nr]=p;
		}
	if (x!=1)
	{
		pr[++nr]=x;
		exp[nr]=1;
	}
}

int putere(int n,int p)
{
	int rez=1,x=n%R;
	while (p)
	{
		if (p&1)
		{
			rez*=(x%R);
			rez%=R;
		}
		x*=(x%R);
		x%=R;
		p>>=1;
	}
	return rez;
}

void calcul()
{
	for (int i=1;i<=nr;++i)
		exp[i]*=b;
	for (int i=1;i<=nr;++i)
	{
		if (pr[i]%a-1!=0)
			s*=(((putere(pr[i],exp[i]+1)-1)%R)*putere((pr[i]%R-1)%R,R-2))%R;
		else
			s*=((exp[i]+1)%R);
		s%=R;
	}
	printf("%d\n",s);
}

int main()
{
	citire();
	desc(a);
	calcul();
	return 0;
}