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

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

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