#include <stdio.h>

#define lgpmax 31
#define MOD 1999999973

long long p[lgpmax];
long long x, n, rez, i;

int main()
{
	// p[i] = x^(2^i)%MOD;
	FILE *fin = fopen("lgput.in", "rt");
	FILE *fout = fopen("lgput.out", "wt");

	fscanf(fin, "%lld %lld", &x, &n);

	p[0] = x;

	for (i = 1; i < lgpmax; i++)
		p[i] = (p[i-1] * p[i-1])%MOD;

	rez = 1;
	for (i = lgpmax - 1; i >= 0; i--)
	{
		while (n >= (1 << i))
		{
			rez *= p[i];
			rez %= MOD;
			n -= (1 << i);
		}
	}
	fprintf(fout, "%lld\n", rez);

	return 0;
}