#include <fstream>
using namespace std;
#define dim 1001
#define mod 9901
int factor[dim], putere[dim];


int solve(int k)
{
	int baza=factor[k];
	int p=putere[k]+1;
	int sol=1;
	
	for(;p;p>>=1)
	{
		if(p&1)
			sol=(sol*baza)%mod;
		baza=(baza*baza)%mod;
	}
	if(sol==-1)
		sol=mod-1;
	else
		--sol;
	int aux=sol;
	p=mod-2;
	baza=factor[k]-1;
	sol=1;
	
	for(;p;p>>=1)
	{
		if(p&1)
			sol=(sol*baza)%mod;
		baza=(baza*baza)%mod;
	}
	
	return (aux*baza)%mod;
}

int main()
{
	ifstream fin("sumdiv.in");
	ofstream fout("sumdiv.out");
	int a, b, aux, u, nr=0,i;
	fin>>a >>b;
	aux=a;
	
	for(i=2;i*i<=a;++i)
		if(aux%i==0)
		{
			factor[++nr]=i;
			while(aux%i==0)
			{
				++putere[nr];
				aux/=i;
			}
			putere[nr]*=b;
		}
	if(aux!=1)
	{
		factor[++nr]=aux;
		putere[nr]=b;
	}
	
	int s=0;
	for(i=1;i<=nr;++i)
		s+=solve(i);
		
	fout<<s;
		
	return 0;
}