#include <stdio.h>
#include <conio.h>
// ridicare la putere in timp logaritmic

int
main()
{

	FILE *fin, *fout;

	unsigned int N, P, C, R;

	C = 1999999973;

	fopen_s(&fin, "lgput.in", "r");

	fscanf_s(fin, "%d %d", &N, &P);

	R = 1;

	while (0 != P)
	{
		if (0 == P % 2)
		{
			N = N * N;
			P = P / 2;
		}
		else
		{
			R = R * N;
			N = N * N;
			P = (P - 1) / 2;
		}

		N = N % C;
	}

	fclose(fin);
	
	fopen_s(&fout, "lgput.out", "w");

	fprintf_s(fout, "%u", R);

	fclose(fout);

	_getch();
	return 0;
}