#include <stdlib.h>
#include <stdio.h>
#define mod 1999999973


int main()
{
	freopen("lgput.in" , "r", stdin);
	freopen("lgput.out" , "w" , stdout);
	
	int i, p;
	long long int c, n;
	
	scanf("%lld %d", &n, &p);
	c = n;
	n=1;
	if(n == 1){
		printf("n\n");
	}
	else{
	for(i = 0 ; (1 << i) <= p ; ++i)
	{
		
		if(p & (1 << i)){
			n = (n*c) % mod;
		}
		c = (c*c) % mod;
	}
	printf("%lld\n", n);
}
	return 0;
}