#include <stdio.h>

#define C 1999999973


int
main()
{

	FILE *fin, *fout;

	unsigned long long  N, P, R;

	fin = fopen("lgput.in", "r");

	fscanf(fin, "%llu %llu", &N, &P);

	R = 1;

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

	fclose(fin);

	fout = fopen("lgput.out", "w");

	fprintf(fout, "%llu", R);

	fclose(fout);

	return 0;
}