#include <stdio.h>

int putere (int n, int p){
	int aux = n, rez = 1, putere = 1;
	while (p){
		while (putere * 2 <= p){
			aux *= aux;
			putere *= 2;
			aux %= 1999999973;
		}
		p = p - putere;
		rez *= aux;
		aux = n;
		putere = 1;
		rez %= 1999999973;
	}
	return rez;
}

int main(){
	freopen ("lgput.in", "r", stdin);
	freopen ("lgput.out", "w", stdout);
	int n, p;
	scanf ("%d%d", &n, &p);
	printf ("%d\n", putere (n, p));
}