#include <iostream>
#define modu 1999999973
FILE * fin= fopen("lgput.in","r");
FILE * fout= fopen("lgput.out","w");

long long n,p;

int main()
{
  fscanf(fin,"%lld %lld",&n,&p);
  long long pown=n;
  long long counn=1;
  long long pow=1;
  while(p!=0)
  {
    if( (p&counn)!=0 )
    {
      pow=(pow*pown)%modu;
      p-=counn;
    }
    counn= counn*2;
    pown=(pown*pown)%modu;
  }
  fprintf(fout,"%lld",pow);
}