#include <iostream>
#include <fstream>
#define k 1999999973
using namespace std;

int main()
{
    ifstream f("lgput.in");
    ofstream g("lgput.out");
    ///Aflati x la puterea n
    long long x,n,r,i,d;
    f>>x>>n;
    /*int var;
    var=2;

    if(var==1)
    {
        r=1;
        for(i=1;i<=n;i++)
            r=(r*x)%k;
    }
    else if (var==2)
    {*/
    int cn=n,biti[33],aux;
    d=0;
    while(n!=0)biti[++d]=n%2,n=n/2;
    n=cn;
    for(i=1; i<=d/2; i++)
    {
        ///Ordonam biti care il formeaza pe n :: switch(biti[i],biti[d-i+1]);
        aux=biti[i];
        biti[i]=biti[d-i+1];
        biti[d-i+1]=aux;
    }
    r=1;
    for(i=1; i<=d; i++)
    {
        r=(r*r)%k;
        if(biti[i]==1)
            r=(r*x)%k;
    }
    //}
    g<<r;
    f.close();
    g.close();
}