#include<stdio.h>

unsigned long i, j, n, p[101], sol, k;
FILE *fin, *fout;

int main()
{
	fin = fopen("lgput.in", "rt");
	fout = fopen("lgput.out", "wt");

	fscanf(fin, "%ld %ld", &n, &k);

	p[0] = n;
	for(i = 1; i <= 32; i++)
	{
		p[i] = (long)(((long long)p[i - 1] * p[i - 1]) % 1999999973);
	}

	sol = 1;
	for(i = 31; i != 0; i--)
	{
		if(k >= ((unsigned long)1 << i))
		{
			k -= ((unsigned long)1 << i);
			sol = (long)(((long long)sol * p[i]) % 1999999973);
		}
	}

	if(k >= ((unsigned long)1 << i))
		{
			k -= ((unsigned long)1 << i);
			sol = (long)(((long long)sol * p[i]) % 1999999973);
		}


	fprintf(fout, "%ld\n", sol);

	return 0;
}