#include <fstream>

using namespace std;
ifstream cin("lgput.in");
ofstream cout("lgput.out");
long long log(long long x,long long y)
{
    if(y<0)
        return log(1/x,-y);
        if(y==0)
        return 1;
    if(y==1)
        return x;
    if(y%2==0)
        return log(x*x,y/2);
    if(y%2==1)

        return log(x*x,(y-1)/2);


}
long long n,p,k;
int main()
{
    cin>>n>>p;
    k=log(n,p);
    cout << k%1999999973;
    return 0;
}