#include <stdio.h>


int main()
{
    long long a,n,p,m,d;
    FILE *f1,*f2;
    f1=fopen("lgput.in","r");
    f2=fopen("lgput.out","w");
    fscanf(f1,"%lld%lld%lld",&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,"%lld",d);
    fclose(f1);
    fclose(f2);
    return 0;
}