#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 sol = 1;
    for (int i = 0; (1 << i) <= P; ++i) {
        if ( ((1 << i) & P) > 0)
            sol = (sol * N) % constant;
        N = (N * N) % constant;
    }
    g << sol;
    return 0x0;
}