#include <fstream>

#define R 1999999973

int main() {
    std::ifstream in("lgput.in");
    std::ofstream out("lgput.out");
    long long n, p, c = 1;
    in >> n >> p;
    n = n % R;
    while (c << 1 <= p) {
        c <<= 1;
        n = (n * n) % R;
    }
    long long r = p - c;
    while (r > 0) {
        if (c > r) c >>= 1;
        else {
            n = ((n >> 1) * n) % R;
            c >>= 1;
            r -= c;
        }
    }
    out << n;
    return 0;
}