#include "stdio.h"

#define M 1999999973

int n, p;
long long a, solution;
unsigned int i;

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

	scanf("%d", &n);
	scanf("%d", &p);

	a = n;
	solution = 1;

	for(i = 0; (i << 1) <= p; ++i)
	{
		if(((i << 1) & p) > 0)
			solution = (solution * a) % M;
		a = (a * a) % M;
	}

	printf("%lld", solution);

	return 0;
}