#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
unsigned long long b,p_dec,m,temp,d;//base, decimal power, binary power, modulo
vector <int> p_bin;
int main(){
    //freopen("lgput.in","r",stdin);
    //("lgput.out","w",stdout);
     
    cin>>b>>p_dec;
     m=1999999973;
    while(p_dec){
        p_bin.push_back(p_dec%2);
        p_dec=p_dec/2;
    }
     d=1;
      
    while(p_bin.size()){
        if(p_bin[p_bin.size()-1]==1)d=((((d%m)*(d%m))%m)*(b%m))%m;
                               else d=((d%m)*(d%m))%m;
        p_bin.pop_back();
         
    }
    cout<<d;
}
 
//Fast Exponential Modulae Arithmetic (FEMA)
//https://www.youtube.com/watch?v=EEsUxxhy50c