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

amr = []

for i in range(n):

    if i == 0:

        x %= m

        amr.append(x)

        continue

    x = pow(x, 2, m)



    if x in amr:

        break

    if x == 0:

        break

    amr.append(x)



if x == 0:

    print((sum(amr[:n])))

else:

    idx = amr.index(x)



    loop = sum(amr[idx:])

    l = len(amr[idx:])



    if n >= idx:

        cnt = (n-idx)//l

        print((cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:])))

    else:

        print((sum(amr[:n])))



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

A = []

al = [-1]*(m+1)

cnt = 0

for i in range(n):

    if al[x%m] >= 0:

        break

    al[x%m] = cnt

    A.append(x)

    cnt += 1   

    x = x**2 % m



if n <= al[x]:

    print((sum(A[:al[x]])))

    exit()



lena = len(A)

loop = A[al[x]:]

lenl = cnt-al[x]

n -= al[x]

cnt = n//lenl

print((sum(A[:al[x]]) + sum(loop)*cnt + sum(loop[:n%lenl])))
n, x, m = list(map(int, input().split()))
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)
    if x in amr:
        break
    if x == 0:
        break
    amr.append(x)
if x == 0:
    print((sum(amr[:n])))
else:
    idx = amr.index(x)
    loop = sum(amr[idx:])
    l = len(amr[idx:])
    if n >= idx:
        cnt = (n - idx) // l
        print((cnt * loop + sum(amr[:idx]) + sum(amr[idx : idx + n - idx - cnt * l :])))
    else:
        print((sum(amr[:n])))

n, x, m = list(map(int, input().split()))
A = []
al = [-1] * (m + 1)
cnt = 0
for i in range(n):
    if al[x % m] >= 0:
        break
    al[x % m] = cnt
    A.append(x)
    cnt += 1
    x = x**2 % m
if n <= al[x]:
    print((sum(A[: al[x]])))
    exit()
lena = len(A)
loop = A[al[x] :]
lenl = cnt - al[x]
n -= al[x]
cnt = n // lenl
print((sum(A[: al[x]]) + sum(loop) * cnt + sum(loop[: n % lenl])))

-amr = [] +A = [] +al = [-1] * (m + 1) +cnt = 0 -    if i == 0: -        x %= m -        amr.append(x) -        continue -    x = pow(x, 2, m) -    if x in amr: +    if al[x % m] >= 0: -    if x == 0: -        break -    amr.append(x) -if x == 0: -    print((sum(amr[:n]))) -else: -    idx = amr.index(x) -    loop = sum(amr[idx:]) -    l = len(amr[idx:]) -    if n >= idx: -        cnt = (n - idx) // l -        print((cnt * loop + sum(amr[:idx]) + sum(amr[idx : idx + n - idx - cnt * l :]))) -    else: -        print((sum(amr[:n]))) +    al[x % m] = cnt +    A.append(x) +    cnt += 1 +    x = x**2 % m +if n <= al[x]: +    print((sum(A[: al[x]]))) +    exit() +lena = len(A) +loop = A[al[x] :] +lenl = cnt - al[x] +n -= al[x] +cnt = n // lenl +print((sum(A[: al[x]]) + sum(loop) * cnt + sum(loop[: n % lenl])))