#include <fstream>

const int MOD(1999999973);

int main (void)
{
	std::ifstream input("lgput.in");
	long long n, p;
	input >> n >> p;
	input.close();
	long long base(n), result(1);
	while (p)
	{
		if (p & 0x01)
			result = (base * result) % MOD;
		base = (base * base) % MOD;
		p >>= 1;
	}
	std::ofstream output("lgput.out");
	output << result << '\n';
	output.close();
	return 0;
}