N, P = map(int, input().split())
mod = 992844353
ans = 1
while N :
	ans *= pow(2, N % P, mod)
	ans %= mod
	N //= P
print(ans)