#include <fstream>
#define mod 1999999973

using namespace std;

 ifstream x ("lgput.in");
 ofstream y ("lgput.out");

 long long N,P;

int main()
{
    x>>N>>P;

    long long i=1,n=N;

    while(i*2<=P)
    {
        i*=2;
        n=n*n%mod;
    }

    if(i==P)
       y<<n<<'\n';
    else
    {
        while(i<P)
        {
            i++;
            n*=N%mod;
        }

        y<<n<<'\n';
    }



    return 0;
}