#include<stdio.h>
unsigned long hcf(unsigned long a,unsigned long b){
    unsigned long r = a % b;
    while(r){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
//recursive version
/*unsigned long fme(unsigned long g,unsigned long x,unsigned long p){
    unsigned long a;
    if(x == 1)
        return g;
    if(x % 2 == 0)
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p ) % p;
    else
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p * g ) % p;
    return a;
}*/
long long fme(long long g,long long x,long long p){
    long long a;
    if(x == 1)
        return g;
    if(x % 2 == 0)
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p ) % p;
    else
        a=( fme(g, x / 2, p) % p * fme(g, x / 2, p) % p * g ) % p;
    return a;
}
int main(int argc, char **argv){
    long long a,b,c;
    long long t;
    FILE *f,*g;
    //Part 1 testing
    /*f = fopen("euclid2.in","r");
    g = fopen("euclid2.out","w");
    fscanf(f,"%lu",&t);
    while(t--){
        fscanf(f,"%lu%lu",&a,&b);
        c = hcf(a,b);
        fprintf(g,"%lu\n",c);
    }
    fclose(f);
    fclose(g);*/

    //Note, for this part, I will implement both an iterative and a
    //recursive version of the algorithm
    //Part 2 testing
    f = fopen("lgput.in","r");
    g = fopen("lgput.out","w");
    long long MOD = 1999999973;
    fscanf(f,"%lld%lld",&a,&b);
    c = fme(a,b,MOD);
    fprintf(g,"%lld",c);
    fclose(f);
    fclose(g);
    return 0;
}