#include<fstream>
#include<cmath>
#include<bitset>
#define MAX 1000005
#include<cstdio>
#define mod 1999999973
#define xxl long long
using namespace std;
long long d,nr,c,s,n,a;
int t;
int p[100005];
bitset <MAX> v;
ifstream f("sumdiv.in");
ofstream g("sumdiv.out");
xxl x,y,sol=1;
int i;
void power(xxl a, xxl b)
{
	for(i=0;(1<<i)<=y;++i)
	{
		if((( 1<<i) & y)>0)
			sol=(sol*x)%mod;
		x=(x*x)%mod;
	}
}
void ciur()
{
	v[1]=1;
	for(int i=2;i<MAX;i++)
	{
		if(v[i]==0)
		{
			p[++p[0]]=i;
			for(int j=i+i;j<=MAX;j+=i)
				v[j]=1;
		}
	}
}
int main()
{
	f>>x>>y;
	power(x,y);
	ciur();
	s=nr=1;
	for(int i=1;(long long)p[i]*p[i]<=sol;i++)
	{
		if(sol%p[i]) continue;
		c=0;
		a=p[i];
		while(sol%p[i]==0)
			sol/=p[i],c++,a=a*p[i];
		nr*=c+1;
		s*=(a-1)/(p[i]-1)%9901;
	}
	if(sol>1)
		nr*=2,s*=(sol+1)%9901;
	g<<s%9973<<"\n";
}