#include <stdio.h>

#define MOD 1999999973

typedef struct {
	unsigned long int N;
	unsigned long int P;
} date_struct;

date_struct get_date(char* file_name) {
	date_struct date;
	FILE *in = fopen(file_name, "r");
	fscanf(in, "%ld %ld", &(date.N), &(date.P));
	fclose(in);
	return date;
}

unsigned long int put_log(unsigned long int N, unsigned long int P) {
	if (P == 0) {
		return 1;
	}
	if (P == 1) {
		return N;
	}
	if (P % 2) {
		return N * put_log(N * N, (P - 1) / 2) % MOD;
	}
	return put_log(N * N, P / 2) % MOD;
}

int main () {
	date_struct date = get_date("lgput.in");
	FILE *out = fopen("lgput.out", "w");
	fprintf(out, "%ld", put_log(date.N, date.P));
	fclose(out);
	return 0;
}