#include<iostream>
#include<fstream>
using namespace std;
#define R 1999999973

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

long long N,P,ANS,FR;

void findR(long long P){
	bool ok=0;
	if(P!=1){
		if(P%2){
			findR(P-1);
		}
		else{
			findR(P/2);
			ok=1;
		}
		if(ok){
			ANS = ( ANS * ANS ) % R;
		}
		else{
			ANS = ( ANS * FR ) % R;
		}
	}
}

int main(){
	
	fin>>N>>P;
	ANS = FR = N % R;
	findR(P);
	
	fout<< ANS;
	
	fin.close();
	fout.close();
	return 0;
}