#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 *= N;
        N *= N;
    }
    g << sol % constant;
    return 0x0;
}