#include <fstream>
#include <cmath>
#include <iostream>
using namespace std;

unsigned long long int p, x, x1, x2, p1, p2, ox1;

int main()
{
	ifstream fin("lgput.in");
	ofstream fout("lgput.out");
	fin >> x >> p;
	x1 = 1;
	x2 = 1;
	x = x % 1999999973;
	if(p > 1)
	{
		p1 = 1;
		x1 = x;
		ox1 = p % 2;
		p = p / 2;
		while(p1 <= p)
		{
			p1 *= 2;
			x1 = x1 * x1;
			if(x1 > 1999999973)
				x1 %= 1999999973;
		}
		p = p * 2 + ox1;
		p2 = p-p1;
		for(p=1; p<=p2; p++)
		{
			x2 = x2 * x;
			if(x2 > 1999999973)
				x2 %= 1999999973;
		}
		fout << x1 * x2 % 1999999973;
	}
	else
	{
		if(p == 0)
			fout << 1;
		else
			fout << x;
	}
	fout.close();
	fin.close();
	return 0;
}