CodeEff/ECCO huggingface dataset:
# Original solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print((pre + cyc + nxt))
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)


# Optimized solution
n, x, m = list(map(int, input().split()))
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(n):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print((pre + cyc + nxt))
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)
# Original solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print((pre + cyc + nxt))
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


# Optimized solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print((pre + cyc + nxt))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
# Original solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print((cyc + remain))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


# Optimized solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        cyc = (sum_p - P[X[x]]) * ((n - X[x]) // cyc_len)
        remain = P[X[x] + (n - X[x]) % cyc_len] 
        print((cyc + remain))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
# Original solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        n -= X[x]
        cyc = (sum_p - P[X[x]]) * (n // cyc_len)
        remain = P[X[x] + n % cyc_len]
        print((cyc + remain))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


# Optimized solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_times, nxt_len = divmod(n-X[x], len(P) - X[x])
        cyc = (sum_p - P[X[x]]) * cyc_times
        remain = P[X[x] + nxt_len]
        print((cyc + remain))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
# Original solution
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)


# Optimized solution
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])))
# Original solution
n,x,m=list(map(int,input().split()))

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print((0))
elif x==1:
    print(n)
elif m==1:
    print((0))
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)
        icnt+=1
    ai0,icnt0,asum0=x,0,0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
#    print("1:",ai,asum,icnt,ai0,asum0,icnt0)
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)       


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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print((0))
elif x==1:
    print(n)
elif m==1:
    print((0))
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)
# Original solution
n,x,m=list(map(int,input().split()))

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print((0))
elif x==1:
    print(n)
elif m==1:
    print((0))
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)       


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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print((0))
elif x==1:
    print(n)
elif m==1:
    print((0))
#elif n<=m*2:
#    asum=x
#    ai=x
#    for i in range(1,n):
#        ai=f(ai,m)
#        asum+=ai
#    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)
# Original solution
def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = list(map(int,input().split()))
c = []
heapq.heapify(c)
cc = []
sisu = 1
count = 0
while True:
    num = pow(x, sisu, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    sisu *= 2
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)

# Optimized solution
def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = list(map(int,input().split()))
c = [x]
heapq.heapify(c)
cc = [x]
num = x
count = 1
while True:
    num = pow(num, 2, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)
# Original solution
n,x,m=list(map(int, input().split()))
a=x
ans=a
flg=[0]*m
flg[a]=1
l=[a]
lp=-1

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != -1:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

# Optimized solution
n,x,m=list(map(int, input().split()))
a=x
ans=a
flg=[0]*m
flg[a]=1
l=[a]
lp=-1

for i in range(1,n):
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != -1:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)
# Original solution
# -*- coding: utf-8 -*-
# map(int, input().split())
N,X,M = list(map(int, input().split()))

first_A = [X]
mod_M = [False for i in range(M)]

is_break = False
for i in range(min(N-1,M+1)):
    A_n1 = pow(first_A[-1],2)%M
    if A_n1 in first_A+[1,0]:
        is_break = True
        last_num = A_n1
        break
    else:
        first_A.append(A_n1)

if is_break:
    if last_num == 0:
        print((sum(first_A)))
    elif last_num == 1:
        nokori = N-len(first_A)
        print((sum(first_A)+nokori))
    else: # roop
        loop_idx = first_A.index(last_num)
        first_A, second_A = first_A[:loop_idx], first_A[loop_idx:]
        roop = int((N-len(first_A))/len(second_A))
        nokori_kaisuu = (N-len(first_A)) - (roop*len(second_A))
        if nokori_kaisuu == 0:
            print((sum(first_A)+(sum(second_A)*roop)))
        else:
            print((sum(first_A)+(sum(second_A)*roop)+sum(second_A[:nokori_kaisuu])))
else:
    print((sum(first_A)))

# Optimized solution
# -*- coding: utf-8 -*-
# map(int, input().split())
N,X,M = list(map(int, input().split()))

first_A = [X]
mod_M = [False for i in range(M+1)]
mod_M[0] = True
mod_M[1] = True

is_break = False
for i in range(min(N-1,M+1)):
    A_n1 = pow(first_A[-1],2)%M
    if mod_M[A_n1]:
        is_break = True
        last_num = A_n1
        break
    else:
        first_A.append(A_n1)
        mod_M[A_n1] = True

if is_break:
    if last_num == 0:
        print((sum(first_A)))
    elif last_num == 1:
        nokori = N-len(first_A)
        print((sum(first_A)+nokori))
    else: # roop
        loop_idx = first_A.index(last_num)
        first_A, second_A = first_A[:loop_idx], first_A[loop_idx:]
        roop = int((N-len(first_A))/len(second_A))
        nokori_kaisuu = (N-len(first_A)) - (roop*len(second_A))
        if nokori_kaisuu == 0:
            print((sum(first_A)+(sum(second_A)*roop)))
        else:
            print((sum(first_A)+(sum(second_A)*roop)+sum(second_A[:nokori_kaisuu])))
else:
    print((sum(first_A)))
# Original solution
N,X,M = list(map(int,input().split()))
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
    if N == len(dps):
      print((sum(dps)))
      break
  else:
    ki = dps.index(d)
    RP = (N-ki) // len(dps[ki:])
    mod = (N-ki) % len(dps[ki:])
    print((sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod])))
    break


# Optimized solution
n, x, m = list(map(int, input().split()))
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print((cyc + remain))
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
# Original solution
n, x, m = list(map(int, input().split()))

cnt = [x]

for i in range(m+1):
    x = x*x % m
    if x in cnt:
        break
    cnt.append(x)

start = cnt.index(x)


ans = sum(cnt[:start])
roop = len(cnt) - start
#print(roop)
n = n-start
ans = ans + (n//roop)*sum(cnt[start:]) + sum(list(cnt)[start:(start+n%roop)])

print(ans)

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

cnt = [x]
c = set()
c.add(x)

for i in range(m+1):
    x = x*x % m
    if x in c:
        break
    cnt.append(x)
    c.add(x)

start = cnt.index(x)

ans = sum(cnt[:start])
roop = len(cnt) - start

n = n-start
ans = ans + (n//roop)*sum(cnt[start:]) + sum(list(cnt)[start:(start+n%roop)])

print(ans)
# Original solution
n, x, m = list(map(int, input().split()))
a = x
mod = [a]
loop = []
cnt = 0
while cnt < n:
    a = a**2 % m
    if a in mod:
        i = mod.index(a)
        before = mod[:i]
        loop = mod[i:]
        break
    mod.append(a)
    cnt += 1

length = len(loop)
if length == 0:
    print((sum(mod[:n])))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)


# Optimized solution
n, x, m = list(map(int, input().split()))
a = x
dup = [0]*(10**5+10)
mod = [a]
loop = []
cnt = 0
while cnt < n:
    a = a**2 % m
    if dup[a]==1:
        i = mod.index(a)
        before = mod[:i]
        loop = mod[i:]
        break
    mod.append(a)
    dup[a] = 1
    cnt += 1

length = len(loop)
if length == 0:
    print((sum(mod[:n])))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)
# Original solution
n, x, m = list(map(int, input().split()))

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)


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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))

is_used = [0] * (m + 1)

count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if is_used[an] == 1:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    is_used[an] = 1
    count = count + an
    pre_an = an

print(count)
# Original solution
n, x, m = list(map(int, input().split()))
mod_list = [-1 for i in range(m)]
value = x
i = 0
head = 0
while i < n:
    if value not in mod_list:
        mod_list[i] = value
        i += 1
        value = (value**2)%m
    else:
        head = mod_list.index(value)
        break
if i == n:
    print((sum(mod_list[:n])))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print((sum(mod_list[:head]) + sum(mod_list[head:i])*block_num + sum(mod_list[head:head+(n-head)%block_size])))

# Optimized solution
n, x, m = list(map(int, input().split()))
mod_value = [-1 for i in range(2*m)] #余りの値を頭から格納
mod_check = [False for i in range(m)] #余りが現れたか否か
value = x
i = 0
head = 0
while i < n:
    if not mod_check[value]:
        mod_value[i] = value
        mod_check[value] = True
        i += 1
        value = (value**2)%m
    else:
        head = mod_value.index(value)
        break
if i == n:
    print((sum(mod_value[:n])))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print((sum(mod_value[:head]) + sum(mod_value[head:i])*block_num + sum(mod_value[head:head+(n-head)%block_size])))
# Original solution
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    if N == 1:
        return X % M
    value = defaultdict(int)
    history = defaultdict(int)
    cur = 0
    cnt = 0
    for i in range(N):
        if X in history:
            break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
    period = i - history[X]
    cur += (N - cnt) // period * (cur - value[X])
    for i in range((N - cnt) % period):
        cur += X
        X = X * X % M
    return cur

if __name__ == '__main__':
    print((solve()))

# Optimized solution
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    if N == 1: return X % M

    cur = 0
    cnt = 0
    value = defaultdict(int)
    history = defaultdict(int)
    for i in range(N):
        if X in history: break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
        
    loop = cur - value[X]
    period = i - history[X]
    freq, rem = divmod(N - cnt, period)
    cur += freq * loop
    for i in range(rem):
        cur += X
        X = X * X % M
    return cur


if __name__ == '__main__':
    print((solve()))
# Original solution
# -*- coding: utf-8 -*-
N, X, M = list(map(int, input().split()))

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:N - 1])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

# Optimized solution
# -*- coding: utf-8 -*-
N, X, M = list(map(int, input().split()))

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if (N - 1) <= counter:
    ans = X + sum(mod_list[:N - 1])
else:
    ans += X + mod_sum
    N -= (counter + 1)
    ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])

print(ans)
# Original solution
N, X, M = list(map(int, input().split()))
A = [X]
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M+1):
  a = a ** 2 % M
  if a in A:
    r0 = A.index(a)
    l = len(A[r0:])
    r = (N - i - 1) // l
    amari = (N - i - 1) % l
    s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
    break
  A.append(a)
  s += A[-1]

print(s)

# Optimized solution
N, X, M = list(map(int, input().split()))
A = [X]
A_dict = {X}
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M+1):
  a = a ** 2 % M
  if a in A_dict:
    r0 = A.index(a)
    l = len(A[r0:])
    r = (N - i - 1) // l
    amari = (N - i - 1) % l
    s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
    break
  A.append(a)
  A_dict.add(a)
  s += A[-1]

print(s)