#include <fstream>

#define BIG 1999999973

using namespace std;

long long N, P, sol = 1;

void Citire(void)
{
	ifstream fin("lgput.in");
	
	fin >>N >>P;
	
	fin.close();
}

void Rezolva(void)
{
	long long i, Pow = N;
	
	for (i = 1; i <= P; i = (i << 1))
	{		
		if (i & P)
			sol = (sol * Pow) % BIG;
 	
		Pow = (Pow * Pow) % BIG;
	}
}

void Afiseaza(void)
{
	ofstream fout("lgput.out");
	
	fout <<sol;
	
	fout.close();
}

int main()
{
	Citire();
	
	Rezolva();
	
	Afiseaza();
	
	return 0;
}