#include <fstream>
#define MODULO 1999999973
std::ifstream in("lgput.in");
std::ofstream out("lgput.out");
int put(long long nr,long long pow)
{
	if(pow==1)
		return nr%MODULO;
	if(pow%2==1)
		return (put(nr,pow/2)*put(nr,pow/2+1))%MODULO;
	else
		return (put(nr,pow/2)*put(nr,pow/2))%MODULO;
}
int main()
{
	long long n,p,i;
	in>>n>>p;
	long long aux = n;
	if(n==0)
	{
		out<<0;
		return 0;
	}
	if(n==1||p==0)
	{
		out<<n;
		return 0;
	}
	if(n%MODULO==0)
	{
		out<<0;
		return 0;
	}
	out<<put(n,p);
	out.close();
	return 0;
}