#include <fstream>
using namespace std;

unsigned long long int p, x, x1, x2;

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