#include <cstdio>

#define MOD 1999999973
long long n, p, sol, P, i;

int main () {

	freopen ("lgput.in", "r", stdin);
	freopen ("lgput.out", "w", stdout);
	
	scanf ("%lld %lld", &n, &p);
	
	P = n; sol = 1;
	for (i = 0; i < 32; i++) {
		if ((p & (1 << i))) 
			sol = (sol * P) % MOD;
		
		P = (P * P) % MOD;
	}
	
	printf ("%lld", sol);
	
	return 0;
}