#include <fstream>
const std::string programName = "lgput";
std::ifstream f(programName + ".in");
std::ofstream g(programName + ".out");
const int constant = 1999999973;
int main() {
    int N, P;
    f >> N >> P;
    int64_t Xcopy, sol = 1;
    Xcopy = N;
    for (int i = 0; (1 << i) <= P; ++i) {
        if ( ((1 << i) & P) > 0)
            sol *= Xcopy;
        Xcopy *= Xcopy;
}
    g << sol % constant;
    return 0x0;
}