CodeEff/ECCO huggingface dataset:
# Original solution
import copy

def culc(k):
    cnt_0=0
    cnt_1=0
    for i in range(r):
        if osenbei1[i][k]==1:
            cnt_1+=1
        else:
            cnt_0+=1
    return max(cnt_0,cnt_1)

def rev(j):
    for i in range(c):
        if osenbei1[j][i]==1:
            osenbei1[j][i]=0
        else:
            osenbei1[j][i]=1
while 1:
    r,c=list(map(int,input().split()))
    if r==c==0:break
    osenbei=[list(map(int,input().split())) for _ in range(r)]
    r_cnt=[[0]*2 for _  in range(r)]
    c_cnt=[[0]*2 for _  in range(c)]
    dp=[[0]*(c+1) for _ in range(1<<r)]
    for i in range(1<<r):
        osenbei1=copy.deepcopy(osenbei)
        for j in range(r):
            if i&(1<<j):
                rev(j)
        for k in range(c):
            dp[i][k+1]=dp[i][k]+culc(k)
    ans=-1
    for i in range(1<<r):
        ans=max(ans,max(dp[i]))
    print(ans)

# Optimized solution
while 1:
    r,c=list(map(int,input().split()))
    if r==c==0:break
    osenbei=[list(map(int,input().split())) for _ in range(r)]
    r_osenbei=[0]*c
    for i in range(c):
        st=""
        for j in range(r):
            st+=str(osenbei[j][i])
        r_osenbei[i]=int(st,2)
    ans=-1
    for i in range(1<<r):
        cnt=0
        for j in range(c):
            n=bin(i^r_osenbei[j]).count('1')
            cnt+=max(n,r-n)
        ans=max(ans,cnt)
    print(ans)
# Original solution
while 1:
    n=eval(input())
    if n==0:break
    t=[list(map(int,input().split())) for i in [1]*n]
    t=sorted(sorted(sorted(t),key=lambda x:x[3])[::-1],key=lambda x:x[2])[::-1]
    u=[0 for i in range(1001)]
    s=0
    for i in t:
    	if (s<10 and u[i[1]]<3) or (s<20 and u[i[1]]<2) or (s<26 and u[i[1]]<1):
    		print(i[0])
    		u[i[1]]+=1
    		s+=1
    

# Optimized solution
while 1:
    n=eval(input())
    if n==0:break
    t=[list(map(int,input().split())) for i in [1]*n]
    t=sorted(sorted(sorted(t),key=lambda x:x[3])[::-1],key=lambda x:x[2])[::-1]
    u=[0]*1001
    s=0
    for i in t:
        if (s<10 and u[i[1]]<3) or (s<20 and u[i[1]]<2) or (s<26 and u[i[1]]<1):
            print(i[0])
            u[i[1]]+=1
            s+=1
# Original solution
# AOJ 1043: Selecting Teams Advanced to Regional
# Python3 2018.7.6 bal4u

def pr(i, u):
	global total
	print((team[i][0]))
	total, affi[u] = total+1, affi[u]+1

while True:
	n = int(eval(input()))
	if n == 0: break
	team = []
	for i in range(n):
		id, u, a, p = list(map(int, input().split()))
		team.append((id, u, a, p))
	team.sort(key=lambda x:(-x[2],x[3],x[0]))
	total, affi = 0, [0]*1002
	for i in range(n):
		u = team[i][1]
		if   total < 10 and affi[u] < 3: pr(i, u)
		elif total < 20 and affi[u] < 2: pr(i, u)
		elif total < 26 and affi[u] < 1: pr(i, u)


# Optimized solution
# AOJ 1043: Selecting Teams Advanced to Regional
# Python3 2018.7.6 bal4u

def pr(i, u):
    global total
    print((team[i][0]))
    total, affi[u] = total + 1, affi[u] + 1


while True:
    n = int(eval(input()))
    if n == 0: break
    team = [list(map(int, input().split())) for i in range(n)]
    team.sort(key=lambda x: (-x[2], x[3], x[0]))
    total, affi = 0, [0] * 1002
    for i in range(n):
        u = team[i][1]
        if   total < 10 and affi[u] < 3: pr(i, u)
        elif total < 20 and affi[u] < 2: pr(i, u)
        elif total < 26 and affi[u] < 1: pr(i, u)
# Original solution
D = {"A":"T","T":"A","C":"G","G":"C"}
b = input().strip()
x = ""
for i in range(len(b)):
    x += D[b[i]]
print(x)

# Optimized solution
b = input().strip()
if b=="A":
    print("T")
elif b=="T":
    print("A")
elif b=="C":
    print("G")
else:
    print("C")
# Original solution
'''
Doubling

nxt[i][r] = the value of r mod M after 2 ** i squaring
dp[i][r] = the sum of sequence of lenght 2 ** i starting from r

We split sequence A into multiple disjoint parts, 
where the lengths of each parts are the binary decomposition of N.

e.g.
N = 11 = 1 + 2 + 8
A = A[0:1], A[1:3], A[3:11]
Sum of each parts are:
sum(A[0:1]) = dp[0][A[0] % M]
sum(A[1:3]) = dp[1][A[1] % M]
sum(A[3:11]) = dp[3][A[3] % M]
'''

import math

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

H = math.ceil(math.log2(N)) + 1

nxt = [[0] * M for _ in range(H)]
dp = [[0] * M for _ in range(H)]
nxt[0] = [r ** 2 % M for r in range(M)]
dp[0] = list(range(M))

for i in range(1, H):
    for r in range(M):
        nxt[i][r] = nxt[i - 1][nxt[i - 1][r]]
        dp[i][r] = dp[i - 1][r] + dp[i - 1][nxt[i - 1][r]]

ans = 0
r = X % M
for i in range(H):
    if N & (1 << i):
        ans += dp[i][r]
        r = nxt[i][r]
print(ans)



# Optimized solution
import math


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

    if N == 1:
        return X % M

    A = [X]
    vis = [-1] * M
    vis[X] = 0
    for i in range(1, M + 1):
        X = X ** 2 % M
        if vis[X] != -1:
            pref = A[:vis[X]]
            cycle = A[vis[X]:]
            break
        A.append(X)
        vis[X] = i

    n_full_period = (N - len(pref)) // len(cycle)
    suffix_length = N - len(pref) - n_full_period * len(cycle)

    ans = 0
    ans += sum(pref)
    ans += sum(cycle) * n_full_period
    ans += sum(cycle[:suffix_length])
    return ans

print((solve()))
# Original solution
N, X, M = list(map(int, input().split()))

Visited = [0]*(M+1)
Mods = [0]*(M+1)
count = 0

for i in range (0, M):
	if (i**2)%M == i:
		Mods[i]=1
        
latest = 0
        
for i in range (0, N):
	if X in Mods:
		count+=((N-i)*X)
		for j in range (0, M+1):
			count+=(j*Visited[j])
		print(count)
		exit()
	if Visited[X] > 0:
		latest = X
		break
	Visited[X]+= 1
	X = (X**2)%M

P = sum(Visited)

for j in range (0, M+1):
	count+=(j*Visited[j])

Visited = [0]*(M+1)

if P == N:
	print(count)
	exit()

crouch = [0]
looper = 0
debu = 0 

for i in range (0, N-P):
	if Visited[X] > 0:
		looper = i
		debu = 1
		break
	else:
		crouch.append(X+crouch[-1])
	Visited[X]+= 1
	X = (X**2)%M
    
if debu == 0:
	for j in range (0, M+1):
		count+=(j*Visited[j])
	print(count)
	exit()
else:
	loops = 0
	for j in range (0, M+1):
		loops+=(j*Visited[j])
	count+=(loops*((N-P)//looper))
	count+=crouch[(N-P)%looper]
print(count)

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

Visited = [0]*(M+1)
latestvisit = [0]*(M+1)
count = 0
latest = 0
proper = 0
        
for i in range (0, N):
	if Visited[X] > 0:
		latest = X
		latestvisit[X] = i
		proper = 1
		break
	latestvisit[X] = i
	Visited[X]+= 1
	X = (X**2)%M

for j in range (0, M+1):
	count+=(j*Visited[j])

if proper == 0:
	print(count)
	exit()
    
P = sum(Visited)
A = latestvisit[X]
B = latestvisit[(X**2)%M]
slouch = 0

for i in range (0, M):
	if latestvisit[i] >=B and latestvisit[i] <= A:
		slouch+=i

count+=((N-P)//(A-B+1))*slouch


for i in range (0, (N-P)%(A-B+1)):
	count+=X
	X = (X**2)%M

print(count)
# Original solution
N, X, M = list(map(int, input().split()))
ans = X
ALL = []
rou = False
for i in range(N-1):
    X = pow(X, 2, M)
    if X in ALL:
        num = ALL.index(X)
        now = i
        rou = True
        break
    ALL.append(X)
    ans += X
if rou :
    roupe = now - num 
    nokori = N - now -2
    print((sum(ALL[num:])*(nokori//roupe) + ans + sum(ALL[num:num + nokori%roupe + 1])))
else:
    print(ans)

# Optimized solution
N, X, M = list(map(int, input().split()))
ans = X
ALL_cal = [False] * M
ALL = []
rou = False
for i in range(N-1):
    X = pow(X, 2, M)
    if ALL_cal[X]:
        num = ALL_cal[X]
        now = i
        rou = True
        break
    ALL.append(X)
    ALL_cal[X] = i
    ans += X
if rou :
    roupe = now - num 
    nokori = N - now - 1
    print((sum(ALL[num:])*(nokori//roupe) + ans + sum(ALL[num:num + nokori%roupe])))
else:
    print(ans)
# Original solution
N, X, M = list(map(int,input().split()))
ans = 0
ls = [X%M] + [-1]*(M+1)
for i in range(N):
    a = ls[i]
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls[i+1] in ls[:i]:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans) 

# Optimized solution
N, X, M = list(map(int,input().split()))
ans = 0
ls = [X%M] + [-1]*(M+1)
ls_app = [0]*(M+1)

for i in range(N):
    a = ls[i]
    ls_app[a] = i
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls_app[ls[i+1]] != 0:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)
# Original solution
n,x,m=list(map(int,input().split()))

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
for i in range(m+1):
    f=pow(2,i)
    p=pow(x,f,m)
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print((t[-1]))
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)


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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    #f*=2
    chk-=1
    if chk==0:
        print((t[-1]))
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)
# Original solution
n,x,m=list(map(int,input().split()))
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print((s[l.index(n)]))
else:
  print((S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)]))

# Optimized solution
n,x,m=list(map(int,input().split()))
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
print((S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)]))
# Original solution
n,x,m=list(map(int,input().split()))
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
d,m=divmod(n-l[x],T)
print((S*d+s[l.index(l[x]+m)]))

# Optimized solution
n,x,m=list(map(int,input().split()))
l,s=[0]*m,[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=p*p%m
k=l[x]
d,m=divmod(n-k,t+1-k)
print(((s[p]+x-s[x])*d+s[l.index(k+m)]))
# Original solution
n, x, m = list(map(int, input().split()))
A = [x]
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in A:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        ans += buf

print(ans)

# Optimized solution
n, x, m = list(map(int, input().split()))
A = [x]
checkA = {x}
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in checkA:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        checkA.add(buf)
        ans += buf

print(ans)
# Original solution
N, X, M = list(map(int,input().split()))
A = [X]
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in A:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

# Optimized solution
N, X, M = list(map(int,input().split()))
A = [X]
As = set(A)
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in As:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
        As.add(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)
# Original solution
# -*- coding: utf-8 -*-

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

A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in A:
        s=A.index(a)
        break
    else:
        A.append(a)

if len(A)==N:
    ans=sum(A)
else:
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    #ans+=sum(A[:s])
    ans+=Z[s]
    #S=sum(A[s:])
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    #ans+=sum(A[s:(s+K)])
    ans+=Z[s+K]-Z[s]


print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

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

A=[0]*10**5
A[0]=X
D=dict()
#A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in D:
        s=A.index(a)
        break
    else:
        #A.append(a)
        A[i]=a
        D[a]=0

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    #ans+=sum(A[:s])
    ans+=Z[s]
    #S=sum(A[s:])
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    #ans+=sum(A[s:(s+K)])
    ans+=Z[s+K]-Z[s]


print(ans)
# Original solution
# -*- coding: utf-8 -*-

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

A=[0]*10**5
A[0]=X
D=dict()
#A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in D:
        s=A.index(a)
        break
    else:
        #A.append(a)
        A[i]=a
        D[a]=0

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    #ans+=sum(A[:s])
    ans+=Z[s]
    #S=sum(A[s:])
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    #ans+=sum(A[s:(s+K)])
    ans+=Z[s+K]-Z[s]


print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

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

A=[0]*(M+1)
A[0]=X
D=[0]*(M+1)

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if D[a] == 1:
        s=A.index(a)
        break
    else:
        A[i]=a
        D[a]=1

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    
    ans=0
    l=len(A)-s
    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])


print(ans)
# Original solution
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = list(map(int, args[0].split()))

    a = x
    ret = 0
    D = [0]*(m+1)
    for i in range(n):
        if 0 < D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))


# Optimized solution
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = list(map(int, args[0].split()))

    a = x
    ret = 0
    D = [-1]*(m+1)
    for i in range(n):
        if 0 <= D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))
# Original solution
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])))



# Optimized solution
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])))
# Original solution
n, x, m = list(map(int, input().split()))
g = x * 1
ans = x
arr = []
res = set([])
roop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		roop = (i, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp

for i, y in enumerate(arr):
	if y == roop[1]:
		k = i
		break

ini = sum(arr[:k])
mul = ans - ini - g
t, v = divmod(n - k - 1, roop[0] - k)
print((g + ini + mul * t + sum(arr[k:k + v])))


# Optimized solution
n, x, m = list(map(int, input().split()))
g = x * 1
ans = x
arr = []
res = set([])
loop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		loop = (i, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp

for i, y in enumerate(arr):
	if y == loop[1]:
		k = i
		break

ini = g + sum(arr[:k])
mul = ans - ini
t, v = divmod(n - k - 1, loop[0] - k)
print((ini + mul * t + sum(arr[k:k + v])))
# Original solution
n, x, m = list(map(int, input().split()))

lst = set()
num = []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i, num.index(x)
        div, mod = divmod(n - cnt, len(num) - idx)
        ans = sum(num[:idx + mod])
        ans += sum(num[idx:]) * (div + 1)
        break
else:
    ans = sum(num)
print(ans)


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

lst, num = set(), []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        break

if x in lst:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans = sum(num[:idx + mod])
    ans += sum(num[idx:]) * (div + 1)
else:
    ans = sum(num)
print(ans)
# Original solution
n, x, m = list(map(int, input().split()))

lst, num = set(), []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        break

ans = sum(num)
if x in lst:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)


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

lst, num = set(), []
for i in range(n):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, num.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:]) * div
    ans += sum(num[idx:idx + mod])
print(ans)
# Original solution
n, x, m = list(map(int, input().split()))

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)


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

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in num:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in num:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)
# Original solution
from collections import defaultdict
N, X, M = list(map(int, input().split()))
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]

ans = 0
# ループの頭の直前まで
ans += sum(A[:iii])
N -= iii
if N > 0:
    # ループの長さ
    l = len(A) - iii
    ans += (N // l) * sum(A[iii:])
    N -= N // l * l
if N > 0:
    # ループに満たないN
    ans += sum(A[iii:iii + N])

print(ans)
exit()


# Optimized solution
from collections import defaultdict
N, X, M = list(map(int, input().split()))
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]

ans = 0

if iii == -1:
    ans = sum(A[:N])
    print(ans)
    exit()
else:
    # ループの頭の直前まで
    ans += sum(A[:iii])
    N -= iii
    if N > 0:
        # ループの長さ
        l = len(A) - iii
        ans += (N // l) * sum(A[iii:])
        N -= N // l * l
    if N > 0:
        # ループに満たないN
        ans += sum(A[iii:iii + N])

    print(ans)
# Original solution
#ダブリング解
n, x, m = list(map(int, input().split()))
tmp = [None]*m
for i in range(m):
    tmp[i] = i*i%m
pos = [tmp]
accu = [tmp]
for i in range(40):
    tmp1 = [None]*m
    tmp2 = [None]*m
    for j in range(m):
        tmp1[j] = pos[-1][pos[-1][j]]
        tmp2[j] = accu[-1][pos[-1][j]] + accu[-1][j]
    pos.append(tmp1)
    accu.append(tmp2)
now = x
ans = x
for i in range(40):
    if (n-1)>>i&1:
        ans += accu[i][now]
        now = pos[i][now]
print(ans)

# Optimized solution
n, x, m = list(map(int, input().split()))
li = [x]
seen = [False]*m
seen[x] = True
for i in range(n-1):
    x = x*x%m
    if seen[x]:
        idx = li.index(x)
        break
    seen[x] = True
    li.append(x)
else:
    print((sum(li)))
    exit(0)
ans = sum(li) + sum(li[idx:])*((n-len(li)) // (len(li)-idx)) + sum(li[idx:idx+(n-len(li)) % (len(li)-idx)])
print(ans)
# Original solution
N, X, M = list(map(int, input().split()))
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count
A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    A = X
    ans = X
    for i in range(N-1):
        A = (A**2)%M
        ans += A
    print(ans)
    exit()

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4

print(ans)

# Optimized solution
N, X, M = list(map(int, input().split()))
if X <= 1:
    print((X*N))
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while A2 != target_value:
    first_count += 1
    A2 = (A2**2)%M

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    print((N*X))
    exit()
if first_count != 0:
    ans = X
    A = X
    for i in range(min(N,first_count)-1):
        A = (A**2)%M
        ans += A
else:
    ans = 0
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)