#include <fstream>
using namespace std;

#define PW(i) (1<<(i))
#define SQ(i) ((i)*(i))
#define R 1999999973

ifstream f("lgput.in");
ofstream g("lgput.out");

int main()
{
	int i, n, p;
	long long a, sol = 1;

	f >> n >> p;
	a = n;
	for (i = 0; PW(i) <= p; ++ i)
	{
		if ( (PW(i) & p) > 0)
			sol = (sol * a) % R;

			a = SQ(a) % R;
	}
	g << sol;
	return 0;
}