#include <iostream>
#include <fstream>

#define MOD 1999999973
using namespace std;

ifstream in ( "lgput.in" );
ofstream out ( "lgput.out" );
int P ;
long long  N ;
long long Sol;


int main ( void ){
   int i ;
   in >> N >> P ;
   Sol = 1 ;
   for ( i = 1; i <= N ; i*= 2 ){
      if ( P&i)
      Sol = ( 1LL*Sol*N) %MOD;
      N = ( 1LL*N*N)%MOD;
      }
   out << Sol ;
   return 0;
}