#include<fstream>
using namespace std;

bool binary[33];
const int MOD = 1999999973;

void dtob(long a,short& i) {
	if (a % 2) binary[i] = true;
	if (a / 2) dtob(a / 2, ++i);
}

int main() {
	ifstream in("lgput.in");
	int x;	long P;
	in >> x >> P;

	short n = 0;
	dtob(P,n);
	long long jelenlegi = x % MOD;
	int result = 1;
	for (short i = 0;i <= n;++i) {
		long long elozo = jelenlegi;
		if (i > 0) 	jelenlegi = (elozo * elozo) % MOD;
		if (binary[i]) 	result = (result * jelenlegi) % MOD;
	}

	ofstream out("lgput.out");
	out << result;
}