#include<stdio.h>

#define INPUT "lgput.in"
#define OUTPUT "lgput.out"
#define MODULO 1999999973
#define LL long long
#define NMAX 10001

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

LL N, P, cont;
LL exp[ NMAX ];

void readValues()
{
  fscanf(fin, "%lld %lld", &N, &P);
}

void makeList()
{
  cont = 0;

  while(P)
  {
    if(P % 2 == 0)
    {
      exp[ ++cont ] = 2;
      P /=2 ;
    }
    else
    {
      exp[ ++cont ] = 1;
      --P;
    }
  }
}

void getValue()
{
  LL prod = 1;

  while(cont)
  {
    if(exp[ cont ] == 2)
      prod = ((prod % MODULO ) * (prod % MODULO)) % MODULO;
    else
      prod = ((prod % MODULO) * (N % MODULO)) % MODULO;

    --cont;
  } 

  fprintf(fout, "%lld\n", prod);
}

int main()
{
  readValues();

  makeList();

  getValue();

  fclose(fin);
  fclose(fout);

  return 0;
}