#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	int mod = 1999999973;
	int N, P, i;

	ifstream in("lgput.in");
	ofstream out("lgput.out");

	in >> N >> P;
	int sol = 1, n = N % mod;
	for(i = 0; i < 32; ++i)
	{
		if((1<<i) & P) {
			sol = (sol * n) % mod; 
		}
		n = (n * n) % mod;
	}
	cout<<sol<<"\n";
	out<<sol<<"\n";
}