def gcd(a, b):
    if a > b:
        a, b, = b, a

    while a:
        a, b = b % a, a
    return b

def pow_mod(a, k, p):
    t = []
    pow_val = 1
    a_pow = a % p
    while pow_val <= k:
        t.append(a_pow)
        a_pow = (a_pow*a_pow) % p
        pow_val <<= 1

    ans = 1
    for i in range(len(t)):
        if k & 1:
            ans = (ans * t[i]) % p
        k >>= 1
    return ans

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break

    tot = 0
    # 累加循环置换的不动点数量
    for k in range(1, n+1):
        d = gcd(k, n)
        tot += pow_mod(m, d, 1<<64)

    if n % 2 == 0:
        tot += (n // 2) * (pow_mod(m, (n+2)//2, 1 <<64) + pow_mod(m, n//2, 1 << 64))
    else:
        tot += n * pow_mod(m, (n-1)//2 + 1, 1 << 64)

    ans = tot // (2*n)
    print(ans)