#include <algorithm>
#define mod 1999999973

using namespace std ;

int max=10001 ;
long long a ;
long long solutie=1 ;
int n ;
long long p ;

int main() {
  freopen ("lgput.in","r",stdin) ;
  freopen ("lgput.out","w",stdout) ;

  scanf ("%d%d" , &n , &p) ;
  a=n ;
  for (int i=0 ; (1<<i)<=p ; ++i) {
    if ( (1<<i)&p )
      solutie=(solutie*a)%mod ;
    a=(a*a)%mod ;
  }
  printf ("%lld" , solutie) ;

  return 0;
}