#include<fstream>
using namespace std;
ifstream cin("lgput.in");
ofstream cout("lgput.out");
#define m 1999999973
long long lgput(int X,int N){
	 if(N==0)  return 1;
	 if (N==1) return X;
	 if(N%2) return X*lgput(X*X,(N-1)/2);
	       else return lgput(X*X,N/2);
}
int main() {
	long long X,P,k;
	cin>>X>>P;
	cout<<lgput(X,P)%m;
	return 0;
}