#include <iostream>
#include <fstream>

std::ifstream fin("lgput.in");
std::ofstream fout("lgput.out");

int main() {
	const int k = 1999999973;
	long long result = 1, currentPower;
	unsigned int n, p;
	fin >> n >> p;

	currentPower = n;

	for (int i = 0; (1 << i) <= p; ++i) {
		if (((1 << i) & p) > 0)
			result = (result * currentPower) % k;
		currentPower = (currentPower * currentPower) % k;
	}

	fout << result << '\n';

	return 0;
}