#include <fstream>
using namespace std;

#define in "lgput.in"
#define out "lgput.out"
#define MOD 1999999973

typedef unsigned long long u;

u n, p, sol = 1, tmp;

u po (u x)
{
	return 1 << x;
}

int main ()
{
	ifstream fin (in);
	fin >> n >> p;
	fin.close();
	tmp = n;
	for (u i = 0; po(i) <= p; ++i) {
		if (po (i) & p)
			sol = (sol * tmp) % MOD;
		tmp = (tmp * tmp) % MOD;
	}
	ofstream fout (out);
	fout << sol;
	fout.close();
	return 0;
}