#include <fstream>
#include <cstring>

#define MODULO 1999999973
#define NMAX 10001

using namespace std;

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

    unsigned int i, n, p;
    long long a, sol = 1;

    fin >> n >> p;

    a = n;

    for(i = 0; (1<<i) <= p; ++i){
        if(((1<<i) & p ) > 0)
            sol = (sol * a) % MODULO;

            a= (a*a) % MODULO;
    }

    fout << sol;
return 0;
}