#include<fstream>
#include<math.h>
using namespace std;
ifstream fin("sumdiv.in");
ofstream fout("sumdiv.out");

struct prim
{
	int valoare, numar;
};
prim V[30];
long a, b, c, x,p,q;
int i, j,k;
int main()
{
	fin >> a >> b;
	i = 2; k = 1;
	
	c = sqrt(a);
	while (i <= c && a>1)
	{
		if (a%i == 0)
		{
			V[k].valoare = i;
			while (a%i == 0)
			{

				V[k].numar++;
				a /= i;
			}
			k++;
		}
		i++;
	}
	if (a != 1) {	V[k].valoare = a; V[k].numar = 1;}
	else k--;

	p = 1; q = 1;
	for (i = 1; i <= k; i++)
	{
		long aux=1;
		c = V[i].numar*b + 1;
		x = V[i].valoare;
		for (int j = 0; (1 << j) <= c; ++j)
		{
			if (((1 << j) & c) > 0) aux = (aux*x) % 9901;
			x = (x*x) % 9901;
		}
		q = (q*(V[i].valoare - 1)) % 9901;
		aux = (9901 + aux - 1) % 9901;
		p *= aux;
	}

	x = q; q = 1;
	for (int j = 0; (1 << j) <= 9899; ++j)
	{
		if (((1 << j) & 9899) > 0) q = (q*x) % 9901; //inversul modular al lui q
		x = (x*x) % 9901;
	}
	q = q % 9901; 
	p = (p*q) % 9901;
	

	fout << p;
	return 0;
}