#include <stdio.h>
#define Mod 1999999973

int n;
int pow[32];
long long p;

int main()
{
	scanf("%d %d", &n, &p);

	pow[0] = n % Mod;
	for (int i = 1; i < 32; i++)
		pow[i] = ((long long)pow[i-1] * pow[i-1]) % Mod;

	int r = 1;
	for (int i = 32 - 2; i >= 0; i--)
	{
		while (p >= ((long long)1 << i))
		{
			r = ((long long)r * pow[i]) % Mod;
			p -= ((long long)1 << i);
		}
	}

	printf("%d\n", r);

	return 0;
}