#include <fstream>
#define MODULO 1999999973
using namespace std;
ifstream fin("lgput.in");
ofstream fout("lgput.out");

int exp(long long a, long long e){

    long long sol = 1;
    for(int i=0;(1<<i)<=e;++i){
        //fout<<sol<<'\n';
        if( ( (1<<i) & e) > 0 )
            sol = (a*sol)%MODULO;

        a = (a*a)%MODULO;
    }

    return sol;

}

int main(){

    long long n, p;
    fin>>n>>p;
    fout<<exp(n, p)%MODULO;

    return 0;
}