p, n = map(int, input().split())

cand = []
for i in range(1, p):
    if i * i > p: break
    if (p - 1) % i != 0: continue
    cand.append(i)
    cand.append((p - 1) // i)

o = p - 1
for c in cand:
    if pow(n, c, p) == 1:
        if c < o:
            o = c

print(((o - 1) * (p - 1) // o) & 1)