from math import gcd

N, B = map(int, input().split())

if gcd(N, B) != 1:
    print('NaN')
    exit()


def factorize(n: int) -> list[int]:
    res = []
    p = 2
    while p * p <= n:
        while n % p == 0:
            res.append(p)
            n //= p
        p += 1
    if n > 1:
        res.append(n)

    return res


def euler_phi(n: int) -> int:
    x = n
    for p in set(factorize(n)):
        x = x * (p - 1) // p
    return x


ans = pow(N, euler_phi(B)-1, B)
print(ans)