#include <stdio.h>
#include <stdlib.h>

#define MOD 1999999973

int exp_log(long long x,long long n){
	if(n < 0) return exp_log(1.0/x,-n);
	if(n == 0) return 1;
	if(n%2 == 0) return exp_log((x*x) % MOD,n/2);
	return x*exp_log((x*x) % MOD,n/2);
}

int main(){

	FILE *f = fopen("lgput.in","r");
	if(f == NULL){
		perror("Eroare la deschidere");
		exit(1);
	}
	FILE *fout = fopen("lgput.out","w");
	if(fout == NULL){
		perror("Eroare la deschidere");
		exit(1);
	}
	
	long long n,p;
	if(fscanf(f,"%lld%lld",&n,&p)!=2){
		perror("Eroare la citire.");
		exit(1);
	}
	
	fprintf(fout,"%d\n",exp_log(n,p) % 1999999973);
	
	fclose(f);
	fclose(fout);
	
	return 0;
}