#include <fstream>

using namespace std;

int logpow(int a,int b, const int& mod) {
	int ret = 1;
	while (b > 0) {
		if (b & 1) {
			ret = 1LL * ret * a % mod;
		}
		a = 1LL * a * a % mod;
		b >>= 1;
	}
	
	return ret;
}

int main() {
	ifstream cin("lgput.in");
	ofstream cout("lgput.out");
	const int mod = 1999999973;
	int N, P;
	cin >> N >> P;
	cout << logpow(N, P % (mod  - 1), mod);
	return 0;
}