// Simionescu Andrei, 3/23/2010
// http://infoarena.ro/problema/lgput
// Dificultate: EASY
// Categorii: matematica

#include <cstdio>
using namespace std;

#define NMAX 10001
#define MMAX 1999999973

unsigned int n, p;
long long aux, res = 1;

int main(){
	freopen( "lgput.in", "r", stdin );
	freopen( "lgput.out", "w", stdout );
	
	scanf("%d %d", &n, &p);
	
	aux = n;
	
	// For each bit of p
	for( int i = 0; (1<<i) <= p; ++i )
	{
        if( ((1<<i) & p) > 0 )
            res = (aux * res) % MMAX;
        
        aux = (aux * aux) % MMAX;
    }
	
	printf("%lld\n", res);
	
	return 0;
}