#include <bits/stdc++.h>
#define mod 1999999973
#define ll long long
using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

long long x, p;

void read() {
	f>>x>>p;
}

ll put(ll a, ll y) {
	if (y == 0) {
		return 1;
	}
	if (y == 1) {
		return a;
	}
	
	if (y%2 == 0) {
		return put((a*a)%mod, y/2)%mod;
	}
	return (a*(put((a*a)%mod, (y-1)/2)%mod))%mod;
}

int main() {
	
	read();
	g<<put(x,p)<<'\n';

	f.close(); g.close();
	return 0;
}