#include <cstdio>
using namespace std;
long long N, P, R, trash;
long long Resolve(long long P, long long rest){
    if(P>1)P=Resolve(P>>1, P&1);
    R*=R;
    R%=1999999973;
    if(P&1)R*=N;
    R%=1999999973;
    return ((P<<1)+rest);
}
int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%lld%lld", &N, &P);
    R=1;
    trash=Resolve(P, P&1);
    printf("%lld", R);
    return 0;
}