#include<fstream>
#define MOD 1999999973
using namespace std;
int exp_log(long long a,int p) {
	int mask=1;
	long long sol=1;
	while(mask<=p) {
		if(mask&p)
			sol=(sol*a)%MOD;
		a=(a*a)%MOD;
		mask*=2;
		}
	return sol;
}
int main() {
	int p;
	long long n;
	ifstream in("lgput.in");
	ofstream out("lgput.out");
	in>>n>>p;
	out<<exp_log(n,p)<<'\n';
	in.close();
	out.close();
	return 0;
}