n, x, m = list(map(int, input().split()))

a = x

S = [0] * (m + 1)

F = [None] * m

F[x] = 0

i0, j0 = None, None

for i in range(1, m + 1):

    S[i] = S[i - 1] + a

    a = pow(a, 2, m)

    if F[a] is not None:

        i0, j0 = F[a], i

    F[a] = i

q, r = (n - i0) // (j0 - i0), (n - i0) % (j0 - i0)

print(((S[j0] - S[i0]) * q + S[i0 + r]))

n, x, m = list(map(int, input().split()))

S = [0]

F = [None] * m

for i in range(m + 1):

    S.append(S[-1] + x)

    if F[x] is not None:

        j = F[x]

        q, r = (n - j) // (i - j), (n - j) % (i - j)

        print(((S[i] - S[j]) * q + S[j + r]))

        exit()

    F[x] = i

    x = pow(x, 2, m)

print((0))

n, x, m = list(map(int, input().split()))
a = x
S = [0] * (m + 1)
F = [None] * m
F[x] = 0
i0, j0 = None, None
for i in range(1, m + 1):
    S[i] = S[i - 1] + a
    a = pow(a, 2, m)
    if F[a] is not None:
        i0, j0 = F[a], i
    F[a] = i
q, r = (n - i0) // (j0 - i0), (n - i0) % (j0 - i0)
print(((S[j0] - S[i0]) * q + S[i0 + r]))

n, x, m = list(map(int, input().split()))
S = [0]
F = [None] * m
for i in range(m + 1):
    S.append(S[-1] + x)
    if F[x] is not None:
        j = F[x]
        q, r = (n - j) // (i - j), (n - j) % (i - j)
        print(((S[i] - S[j]) * q + S[j + r]))
        exit()
    F[x] = i
    x = pow(x, 2, m)
print((0))

-a = x -S = [0] * (m + 1) +S = [0] -F[x] = 0 -i0, j0 = None, None -for i in range(1, m + 1): -    S[i] = S[i - 1] + a -    a = pow(a, 2, m) -    if F[a] is not None: -        i0, j0 = F[a], i -    F[a] = i -q, r = (n - i0) // (j0 - i0), (n - i0) % (j0 - i0) -print(((S[j0] - S[i0]) * q + S[i0 + r])) +for i in range(m + 1): +    S.append(S[-1] + x) +    if F[x] is not None: +        j = F[x] +        q, r = (n - j) // (i - j), (n - j) % (i - j) +        print(((S[i] - S[j]) * q + S[j + r])) +        exit() +    F[x] = i +    x = pow(x, 2, m) +print((0))