#include<fstream>
using namespace std;

#define modulo 1999999973


int exponent(int, int);

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

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

	return 0;
}

int exponent(int n, int 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);
}