#include <cstdio>
#include <cmath>

using namespace std;

FILE * iFile;
FILE * oFile;

long long n, p, a, sol, m;

void read()
{
	fscanf(iFile, "%lld %lld", &n, &p);
}

void solve()
{
	long long i;
	
	a = n;
	sol = 1;
	m = 1999999973;
	
	for(i=0;(1 << i) <= p; ++i)
	{
		if(((1 << i) & p) > 0)
			sol = (sol * a) % m;
		a = (a * a) % m;
	}	
}

void write()
{
	fprintf(oFile, "%lld", sol);	
}

int main()
{
	iFile = fopen("lgput.in", "r");
	oFile = fopen("lgput.out", "w");
	
	read();
	solve();
	write();
	
	fclose(iFile);
	fclose(oFile);
	
	return 0;
}