N,B=map(int,input().split())
e=C=B
i=2
while i*i<=B:
	if C%i<1:
		e=e//i*(i-1)
		while C%i<1:C//=i
	i+=1
if C>1:e=e//C*(C-1)
N%=B
e-=1
p=1%B
q=N
while e:
	if e%2:p=p*q%B
	q=q*q%B
	e//=2
print(["NaN",p][(p*N-1)%B<1])