/* x^n=(x^n/2)^2 n<=par
x^n=x*(x^n/2)^2 n<=par*/
#include <fstream>
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");
long long int rez=1,n,px,r,x,pz;
int main()
{
	fin>>x>>n;
	px=x;
	pz=x*x;
	while(n>0)
	{
		r=n%2;
		if(r)rez *=px;
		n=n/2;
		px=px*px;
		//if(r) rez=rez*x;
		if(r=0)rez*=pz;
		rez=rez%1999999973;
	}
	fout<<rez;;
}