//Ridicare la putere in timp logaritmic
#include <stdio.h>
#define INPUT "lgput.in"
#define OUTPUT "lgput.out"
#define CONST 1999999973

long long n, p;
int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%lld %lld", &n, &p);
	unsigned int i;
	long long sol = 1;
	
	for(i = 0; 1<<i <= p; ++i, n=(n*n)%CONST)
		if(1<<i & p)
			sol = (sol * n) % CONST;

	printf("%lld\n", sol);
	return 0;
}