#include <fstream>
using namespace std;

ifstream f1("lgput.in");
ofstream f2("lgput.out");

int mod = 1999999973;
int n, p, p2, i;
long long v[33], rez=1;
int main()
{
    f1>>n;
    f1>>p;
    v[0]=n;
    i=1;
    p2=2;
    while (p2<=p)
    {
        v[i]=(v[i-1]*v[i-1])%mod;
        p2*=2;
        i++;
    }
    p2/=2;
    i--;
    while (p!=0)
    {
        if(p>=p2)
        {
            p-=p2;
            rez=(rez*v[i])%mod;
        }
        p2/=2;
        i--;
    }
    f2<<rez;
}