#include <cstdio>

#define PRIM 1999999973

long long N, P, Ans, tmp;

int main () {
	freopen ("lgput.in", "r", stdin);
	freopen ("lgput.out", "w", stdout);
   
	scanf ("%lld %lld\n", &N, &P);
    for (long long step = Ans = 1, tmp = N; P; step <<= 1){
		if (P & step){
		   	Ans = (Ans * tmp) % PRIM;
			P -= step;
		}
		tmp = (tmp * tmp) % PRIM; 
		//printf ("%lld %lld\n", Ans, tmp);
	}

	printf ("%lld\n", Ans);

	return 0;
}