#include <fstream>
using namespace std;

ifstream f("lgput.in");
ofstream g("lgput.out");

long long n,p,rez;
int v[33],imax;
int A[33];

void biti(int n)
{
    int i,m=1;
    for(i=1;i<=30;i++)
    {
        if((m&n)==m) {v[i]=1; imax=i;}
        m=(m<<1);
    }
}

void calc(int n)
{
    int i;
    for(i=2;i<=n;i++) A[i]=(A[i-1]*A[i-1])%1999999973;
}

int main()
{
    int i;
    f>>n>>p;

    A[1]=n;
    biti(p);
    calc(imax);

    rez=A[imax];
    for(i=1;i<imax;i++) if(v[i]==1) rez=(rez*A[i])%1999999973;

    g<<rez<<"\n";

    f.close();
    g.close();
    return 0;
}