#include<fstream>
using namespace std;
ifstream f("lgput.in");
ofstream g("lgput.out");
long long N,K,M,rez;
int main(){
	f>>N>>K;
    M=N;
    rez=1;
    for(int i=0;1LL*(1<<i)<=K;++i){
        if((1<<i)&K){
            rez*=M;
            rez%=1999999973;
        }
        M*=M;
        M%=1999999973;
    }
   g<<rez<<'\n';
   g.close();
   return 0;
}