#include <fstream>

using namespace std;

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

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