#include <fstream>
#include <math.h>
using namespace std;
ifstream in("lgput.in");
ofstream out("lgput.out");
int main()
{
    long long n,x,p,r;
    in>>n;
    in>>p;
    if(p%4==0)
    {
        x=pow(n,4);
        r=x%1999999973;
    }
    if(p%4==1)
    {
        x=pow(n,1);
        r=x%1999999973;
    }
    if(p%4==2)
    {
        x=pow(n,2);
        r=x%1999999973;
    }
    if(p%4==3)
    {
        x=pow(n,3);
        r=x%1999999973;
    }
    out<<r;
    return 0;
}