#include <fstream.h>

int main()
{
	unsigned int p;
	unsigned long long x,result=1;
	
	ifstream in("lgput.in");
	in>>x>>p; in.close();
	while(p>0)
	{
		if(p%2==1){ result=(result*x)%1999999973; --p; } //p impar;
		x=(x*x)%1999999973; p=p/2; // p/=2;
	}
	ofstream out("lgput.out"); out<<result; out.close();
	
	return 0;
}