#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() {
	long x, P;					//
	ifstream in("lgput.in");
	ofstream out("lgput.out");
	in >> x >> P;
	short n = 0;
	dtob(P,n);
	long long *szorzat = new long long[n+1];
	szorzat[0] = x % MOD;
	long long result = 1;
	for (int i = 0;i <= n;++i) {
		if (i > 0) {
			szorzat[i] = (szorzat[i - 1] * szorzat[i - 1]) % MOD;
			szorzat[i] %= MOD;
		}
		if (binary[i]) result *= szorzat[i];
	}
	out << result;
}