#include <fstream>
using namespace std;

#define PRIME 1999999973

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

int i, a, b, n, k, p;
long long d;
bool bin[33];

int main(){

	fin >> a >> b;
	n = PRIME;

	i = 0;
	while (b) { bin[i++] = b % 2;  b /= 2; }

	k = i - 1;	p = 0;  d = 1;
	for (i = k; i >= 0; i--){
		p = 2 * p;
		d = (d*d) % n;
		if (bin[i]){
			d = (d*a) % n;
		}
	}

	fout << d;

	return 0;
}