#include <stdio.h>
#define MAX 1999999973

long int lgput(int n, int p, int r) {
	if (p == 1) {
		return r;
	}
	r %= MAX;
	r *= r;
	if (p & 1) {
		r *= n;
	}
	return lgput(n, p/2, r);
}

int main() {
	int n, p;
	FILE* in = fopen("lgput.in", "rt");
	if (in == NULL) {
		printf("Nu am putut deschide fisierul de input!\n");
		return -1;
	}
	FILE* out = fopen("lgput.out", "wt");
	if (out == NULL) {
		printf("Nu am putut deschide fisierul de output!\n");
		return -2;
	}
	fscanf(in, "%d %d", &n, &p);
	fprintf(out, "%ld\n", lgput(n, p, n));
	fclose(in);
	fclose(out);
	return 0;
}