#include <stdio.h>
#include <string.h>

#define MOD 1999999973;

int N, P;

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

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

	int bit;
	long long Res = 1, power_of_N = N;
	for (bit=0; (1 << bit) <= P; bit++)
	{
		if ((1 << bit) & P)
			Res = (Res * power_of_N) % MOD;
		power_of_N = (power_of_N * power_of_N) % MOD;
	}

	fprintf(fout, "%lld", Res);

	return 0;
}