#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;
	
}