#include <fstream>

using namespace std;

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


const int k = 1999999973;
int n, p, i, sol;

int main(){
    fin >> n >> p;
    sol = 1;
    for (i=0; (1<<i)<=p; i++){
        if (((1<<i) & p) > 0){
            sol = (sol*n)%k;
        }
        n = (n * n)%k;
    }
    fout << sol;
    return 0;
}