#include <stdio.h>
#include <assert.h>

#define MOD 1999999973
#define ll long long

ll N, P;

ll compute(ll p)
{
	if (p == 0)
		return 1;
	
	ll x = compute(p/2);
	x = (x * x) % MOD;
	if (p % 2)
		x = (x * P) % MOD;
		
	return x;		
}

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

	scanf("%lld %lld", &N, &P);
	assert(2 <= N && N <= (ll)1<<32);
	assert(2 <= P && P <= (ll)1<<32);

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