/*
 * putere.c
 *
 *  Created on: Jan 1, 2014
 *      Author: ciprian
 */
#include<stdio.h>
#include<stdlib.h>

const int NR=1999999973;

long putere(long X, long N) {
	if (N < 0)
		return putere(1 / X, -N);
	if (N == 0)
		return 1;
	if (N == 1)
		return X;
	else if (N % 2 == 0)
		return putere(X * X, N / 2);
	return X * putere(X * X, (N - 1) / 2);

}

int main() {

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

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

	fprintf(fout,"%lld",(putere(N,P))%NR);

	return 0;
}