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

using namespace std;

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

long long var;

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

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