#include <fstream>

using namespace std;

ifstream cin("lgput.in");
ofstream cout("lgput.out");

int v[65];
int main()
{
    int n,i,cat,p,j,r;
    cin>>n>>p;
    r=1;
    i=0;
    while(p!=0){
        cat=p/2;
        i++;
        v[i]=p%2;
        p/=2;
    }
    for(j=i;j>=1;j--){
        r=r*r;
        if(v[j]==1)
            r*=n;
        r%=1999999973;
    }
    cout<<r;
    return 0;
}