#include <cstdio>

#define MOD 1999999973

long long unsigned compute(long long unsigned n, long long unsigned p)
{
	if(!p)
		return 1;
	long long unsigned t = compute(n, p>>1);
	if(p & 1)
		return (((t * t) % MOD) * n) % MOD;
	else
		return (t * t) % MOD;
}

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

	long long unsigned n, p;
	scanf("%llu %llu", &n, &p);
	printf("%llu", compute(n, p));

	fclose(stdin);
	fclose(stdout);
	return 0;
}