#include <fstream>
#define MOD 1999999973
using namespace std;
ifstream fi("lgput.in");
ofstream fo("lgput.out");

long long n,p,rez;

long long sqr(long long last_ans)
{
    return (last_ans*last_ans)%MOD;
}

int main()
{
    long long last_ans;
    fi>>n>>p;
    last_ans=n%MOD;
    rez=1;
    for (int i=0; (1LL<<i)<=p; i++)
    {
        if (p&(1LL<<i))
            rez=(rez*last_ans)%MOD;
        last_ans=sqr(last_ans);
    }
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}