#include <fstream>

#define R 1999999973

long long v[33], vp[33];

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