#include<cstdio>
const int MOD = 1999999973;
int main()
{
  freopen("lgput.in","r",stdin);
  freopen("lgput.out","w",stdout);
  long long n , p;
  long long rez = 1;
  scanf("%lld%lld",&n,&p);
  long long inm = n;
  for(long long i = 0 ; (1 << i) <= p ; i ++)
  {
    if(( (1 << i) & p) > 0)
    {
      rez = (rez * inm) % MOD;
    }
    inm = (inm * inm) % MOD;
  }
  printf("%lld",rez);
return 0;
}