#include <stdio.h>

#define MOD 1999999973

int main()
{
	freopen("lgput.in", "rt", stdin);
	freopen("lgput.out", "wt", stdout);

	long long N, P;
	scanf("%lld %lld", &N, &P);

	if (P == 0)
	{
		printf("1\n");
		return 0;
	}

	long long rez = 1;
	for (int k = 0; 1LL << k <= P; k++)
	{
		if (P & (1LL << k))
			rez *= N, rez %= MOD;

		N *= N, N %= MOD;
	}
	printf("%lld\n", rez);

	return 0;
}