#include <iostream>
#include <fstream>

#define M 1999999973

using namespace std;

long power (long n, long p) {	
	long r = 1, temp = n, checkbit = 1;
	while (checkbit <= p) {
		if (checkbit & p) r *= temp;
		temp *= temp;
		checkbit <<= 1;
	}
	
	return r;
}
	
	
	
int main (void) {
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);
	
	long n, p;
	cin >> n >> p;
	cout << power(n,p) % M;
	
	return 0;
}