// Ridicare la putere in timp logaritmic 

#include <fstream>
#define MOD 1999999973
using namespace std;
int main(){
    int N,P,i;
    long long Fact, Sol=1;
    ifstream in("lgput.in");
    ofstream out("lgput.out");
    in>>N>>P;
    Fact=N;
    for(i=0; (1<<i)<= P; i++){
     if(((1<<i)&P)>0) 
      Sol=(Sol*Fact)%MOD;
     Fact=(Fact*Fact)%MOD;
    }
    out<<Sol<<"\n";
    in.close();
    out.close();
    return 0;
    
}