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

int m=1999999973;;

int main() {
	FILE *fin,*fout;
	int n,p,i;
	long a,sol=1;


	fin=fopen("lgput.in","r");
	fout=fopen("lgput.out","w");
	fscanf(fin,"%d",&n);
	fscanf(fin,"%d",&p);

	a=n;
		for(i=0;(1<<i)<=p; i++) {	// 1<<i o sa produce pe rand 0,2,4,8,16

			if(((1<<i) & p )> 0)
				sol=(sol*a)%m;
			a=(a*a) % m;

		}

		fprintf(fout,"%ld",sol);


	return 0;
}