#include <iostream>
#include <fstream>

using namespace std;

unsigned long N,
			  P;

int main(int argc, char *argv[]) {
	ifstream fin("lgput.in");
	fin >> N >> P;
	fin.close();

	unsigned long i = 1 << 31;
	unsigned long sol = 1;
	while (i > 0) {
		sol = (sol * sol) % 1999999973;
		if (i & P)
			sol = (sol * N) % 1999999973;
		//cout << i << " " << (i & P) << " - " << sol << endl;
		i >>= 1;
	}

	ofstream fout("lgput.out");
	fout << sol << endl;
	fout.close();

	return 0;
}