#include<iostream>
#include<fstream>
#define modulo 1999999973

using namespace std;

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

long long lgput(long long int N, long long int P)
{	
	if(P==0)
		return 1;
	else
		if(P%2==1)
			return (N*lgput(N,(P-1)/2)*lgput(N,(P-1)/2))%modulo;
		else
			return (lgput(N,P/2)*lgput(N,P/2))%modulo;
			
}
	
long long int N,P,result;

int main()
{
	fin>>N;
	fin>>P;
	result=lgput(N,P);
	fout<<result;
	return 0;
}