#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 *szorzat = new long long[n+1];
	szorzat[0] = x % MOD;
	int result = 1;
	for (int i = 0;i <= n;++i) {
		if (i > 0) 	szorzat[i] = (szorzat[i - 1] * szorzat[i - 1]) % MOD;
		if (binary[i]) 	result = (result*szorzat[i]) % MOD;
	}

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