#include <stdio.h>

#define MODULO 1999999973

long long n, p, r = 1;

void putere(int p)
{
     if ( p >= 1)
     {
          if ( p % 2 == 0)
          {
               putere( p / 2);
               r = ( r * r) % MODULO;
           }
           else
           {
               putere( p - 1);
               r = ( r * n ) % MODULO;
           }
      }
}


int main()
{
    freopen("lgput.in", "r", stdin);
    freopen("lgput.out", "w", stdout);
    scanf("%lld %lld", &n, &p);
    putere(p);
    printf("%lld\n", r);
    return 0;
    }