#include <fstream>
#define W 1999999973

using namespace std;

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

long long exp_log(long long x, long long P);

long long n, p;

int main()
{
	fin >> n >> p;
	fout << exp_log(n, p);
	return 0;
}

long long exp_log(long long x, long long P)
{
	long long nr;

	if (P == 1)
		return x%W;
	if (P % 2)
		return (x%W*exp_log(x, P - 1))%W;
	nr = exp_log(x, P / 2);
	return (nr%W)*(nr%W)%W;
}