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