#include<cstdio>
#include<fstream>

using namespace std;

#define nn 50
#define mod 1999999973

int b[nn];
long long n,p;

int main ()
{

ifstream in ("lgput.in");
freopen("lgput.out","w",stdout);
in>>n>>p;
in.close();
int nm=0;
for(;p;p/=2)
b[++nm]=p%2;
long long rez=1;
for(;nm;--nm){
rez*=rez;
if(b[nm])
rez*=n;
}
printf("%lld\n",rez%mod);

return 0;}