N, X, M = list(map(int, input().split()))



candicate = [pow(i, 2, M) for i in range(M)]

ans = 0

now = X

A = [0]

X2 = pow(X, 2, M)



d = dict()



flag = True

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

    if i == 1:

        A.append(X)

    

    else:

        nxt = candicate[A[i-1]]



        if d.get(nxt) == None:

            if nxt == 0:

                A.append(nxt)

                break

            else:

                A.append(nxt)

                d[nxt] = i



        else:

            flag = False

            break





if flag:

    print((sum(A)))

else:

    l = d[nxt]

    r = i - 1

    circle_total = 0

    for j in range(l, r+1):

        circle_total += A[j]

    

    for j in range(1, l):

        ans += A[j]



    width = r - l + 1

    N -= (l - 1)

    ans += circle_total * (N // width)



    for j in range(l, l + N % width):

        ans += A[j]



    print(ans)

N,X,M = list(map(int,input().split()))



ans = X

A = X

TF = True

srt = 1000000

retu = [X]

d = dict()

d[X] = 0

loop = X

flag = False

for i in range(N-1):

    if TF:

        A = A**2 % M

        if d.get(A) != None:

          srt = d[A]

          goal = i

          TF = False

          

        if TF:

          retu.append(A)

          d[A] = i + 1

          loop += A

    else:

      flag = True

      break

      

if flag:

    n = (N-srt)//(goal-srt+1)

    saisyo = sum(retu[:srt])

    loop -= saisyo

    print((saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)])))

    

else:

    print((sum(retu[:N])))

N, X, M = list(map(int, input().split()))
candicate = [pow(i, 2, M) for i in range(M)]
ans = 0
now = X
A = [0]
X2 = pow(X, 2, M)
d = dict()
flag = True
for i in range(1, N + 1):
    if i == 1:
        A.append(X)
    else:
        nxt = candicate[A[i - 1]]
        if d.get(nxt) == None:
            if nxt == 0:
                A.append(nxt)
                break
            else:
                A.append(nxt)
                d[nxt] = i
        else:
            flag = False
            break
if flag:
    print((sum(A)))
else:
    l = d[nxt]
    r = i - 1
    circle_total = 0
    for j in range(l, r + 1):
        circle_total += A[j]
    for j in range(1, l):
        ans += A[j]
    width = r - l + 1
    N -= l - 1
    ans += circle_total * (N // width)
    for j in range(l, l + N % width):
        ans += A[j]
    print(ans)

N, X, M = list(map(int, input().split()))
ans = X
A = X
TF = True
srt = 1000000
retu = [X]
d = dict()
d[X] = 0
loop = X
flag = False
for i in range(N - 1):
    if TF:
        A = A**2 % M
        if d.get(A) != None:
            srt = d[A]
            goal = i
            TF = False
        if TF:
            retu.append(A)
            d[A] = i + 1
            loop += A
    else:
        flag = True
        break
if flag:
    n = (N - srt) // (goal - srt + 1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print((saisyo + loop * n + sum(retu[srt : N - n * (goal - srt + 1)])))
else:
    print((sum(retu[:N])))

-candicate = [pow(i, 2, M) for i in range(M)] -ans = 0 -now = X -A = [0] -X2 = pow(X, 2, M) +ans = X +A = X +TF = True +srt = 1000000 +retu = [X] -flag = True -for i in range(1, N + 1): -    if i == 1: -        A.append(X) +d[X] = 0 +loop = X +flag = False +for i in range(N - 1): +    if TF: +        A = A**2 % M +        if d.get(A) != None: +            srt = d[A] +            goal = i +            TF = False +        if TF: +            retu.append(A) +            d[A] = i + 1 +            loop += A -        nxt = candicate[A[i - 1]] -        if d.get(nxt) == None: -            if nxt == 0: -                A.append(nxt) -                break -            else: -                A.append(nxt) -                d[nxt] = i -        else: -            flag = False -            break +        flag = True +        break -    print((sum(A))) +    n = (N - srt) // (goal - srt + 1) +    saisyo = sum(retu[:srt]) +    loop -= saisyo +    print((saisyo + loop * n + sum(retu[srt : N - n * (goal - srt + 1)]))) -    l = d[nxt] -    r = i - 1 -    circle_total = 0 -    for j in range(l, r + 1): -        circle_total += A[j] -    for j in range(1, l): -        ans += A[j] -    width = r - l + 1 -    N -= l - 1 -    ans += circle_total * (N // width) -    for j in range(l, l + N % width): -        ans += A[j] -    print(ans) +    print((sum(retu[:N])))