#include <fstream>
using namespace std;

#define in "lgput.in"
#define out "lgput.out"

const long int MOD = 1999999973;
long int N, P;

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

	scanf ( "%ld%ld", &N, &P );

	int i;
	long int result = 1;
	long int A = N;
	for ( i = 0; (1L<<i) <= P; ++i )
	{
		if ( P & (1L<<i) > 0) { result = ((result * A)%MOD); }
		A = ( ( A * A ) % MOD );
	}

	printf ( "%ld\n", result );
	return 0;
}