#include <fstream>
using namespace std;

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

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

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

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

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

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