#include <fstream>
#define MODULO 1999999973
std::ifstream in("lgput.in");
std::ofstream out("lgput.out");
long long power(long long baza,long long exp)
{
	if(exp==1)
		return baza%MODULO;
	else
	if(exp%2==1)
		return ((baza%MODULO)*power(baza,exp-1)%MODULO)%MODULO;
	else
	{
		long long x = power(baza,exp/2)%MODULO;
		return x*x;
	}
}
int main()
{
	long long n,p;
	in>>n>>p;
	if(n==0)
	{
		out<<0;
		return 0;
	}
	if(n==1||p==0)
	{
		out<<1;
		return 0;
	}
	if(n%MODULO==0)
	{
		out<<0;
		return 0;
	}
	n%=MODULO;
	out<<power(n,p)%MODULO;
	out.close();
	return 0;
}