#include <fstream>

std::ifstream in("lgput.in");
std::ofstream out("lgput.out");

#define num 1999999973

uint64_t n, p, v[32];

int main() {
    in >> n >> p;

    v[0] = n;
    for (int i = 1; i < 32; i++) {
        v[i] = v[i - 1] * v[i - 1];
        v[i] %= num;
    }

    uint64_t ans = 1;
    for (int i = 0; p > 0; i++, p >>= 1) {
        if (p & 1) {
            ans *= v[i];
            ans %= num;
        }
    }

    out << ans;
}