#include <stdio.h>
#include <math.h>

#define M  1999999973

long long unsigned exp_log_rec(unsigned n, unsigned p){
 if(p < 0) return exp_log_rec(1 / n, -p);
 if(p == 0) return 1;
 if(p % 2 == 0) return exp_log_rec(n*n%M, p/2);
 if(p % 2 == 1) return n * exp_log_rec(n*n%M, p/2)%M;

 return 0;
}

int main(){
    long long unsigned n;
    long long unsigned p;
    freopen("lgput.in" , "r" , stdin);
    freopen("lgput.out" , "w" , stdout);
    if(scanf("%lld %lld" , &n , &p) == 2){
        printf("%lld" , exp_log_rec(n,p));
        //printf("%ld" , sizeof(unsigned long));
    }
    return 0;
}