#include<fstream>
using namespace std;

#define modulo 1999999973


long long exponent(long long, long long);

int main()
{
	ifstream fin("lgput.in");
	ofstream fout("lgput.out");

	unsigned long long n, p;
	fin >> n >> p;
	
	fout << exponent(n, p) % modulo;

	system("pause");
	return 0;
}

long long exponent(long long n, long long p)
{
	if (p == 0)
		return 1;
	if (p == 1)
		return n;

	if (p & 1)
		return n * exponent(n * n, (p - 1) / 2);
	else
		return exponent(n * n, p / 2);
}