#include <stdio.h>
#define M 1999999973


int N, P;

int power(int N, int P)
{	
	int p = 1;
	int res = N;

	if (P == 0)	return 1;

	while (p <= P/2) {
		res *= res;
		p *= 2;
	}
	
	if (p == P)		return res;
	if (p*2 == P) 	return res * res;
					return res * res * N;
}


int main()
{
	freopen("lgput.in", "r", stdin);
	freopen("lgput.out", "w", stdout);

	scanf("%d %d", &N, &P);
	printf("%d\n", power(N, P) % M);

	return 0;
}