#include <stdio.h>


int main()
{
    int a,n,p,m,d;
    FILE *f1,*f2;
    f1=fopen("lgput.in","r");
    f2=fopen("lgput.out","w");
    fscanf(f1,"%d%d%d",&a,&n,&p);
	m=1999999973;
	p=1;
    while(n!=0){
                if(n%2!=0) 
                            p=p*a%m;
                a=a*a;
                n=n/2;
                };
	d=p%m;
    fprintf(f2,"%d",d);
    fclose(f1);
    fclose(f2);
    return 0;
}