#include<cstdio>
using namespace std;
int i, n, k, x, j, baza;
long long prod;
int main(){
    freopen("lgput.in","r",stdin);
    freopen("lgput.out","w",stdout);
    scanf("%d%d", &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;
}