#include <stdio.h>
#define MOD	1999999973

long long N, P;

long long power(long long N, long long P) {
	
	if (P == 0)
		return 1;

	long long temp = power(N, (P >> 1)) % MOD;

	if (P % 2 == 0)
		return (temp * temp) % MOD;
	else
		return (N * temp * temp) % MOD;
}

int main(void) {

	FILE *fin = fopen("lgput.in", "r");
	FILE *fout = fopen("lgput.out", "w");

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

	fprintf(fout, "%llu", power(N, P));
	fclose(fout);

	return 0;
}