#include<cstdio>
#define MOD 1999999973
using namespace std;
long long n, p, putere, rez, i;
int main(){
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%lld%lld", &n, &p);
    putere=n; rez=1;
    for (i=0;(1<<i)<=p;i++) {
        if (((1<<i)&p)>0) rez=(rez*putere)%MOD;
        putere=(putere*putere)%MOD;
    }
    printf("%lld\n", rez);
    return 0;
}