#include <stdio.h>
#include <string.h>
#include<fstream>
using namespace std;
ifstream f("sumdiv.in");
ofstream g("sumdiv.out");
const int n_max = 10001;
const int m = 1999999973;
unsigned int i, n, p,k,q;
long long a, sol = 1;
long long sum=0;
int s=0;
inline void maxpower(int x,int y)
{
	int a=x;
	for (int i = 0; (1<<i) <= y; ++ i)
	{
		if ( ((1<<i) & y) > 0)
			sol= (sol * a) % m;
			a=(a * a) % m;
	}
}
int main()
{
	f>>n>>k;
	maxpower(n,k);
	for(i=1;i<=sol;i++)
		if(sol%i==0)
			s+=i;
	g<<s%9901;
}