CodeEff/ECCO huggingface dataset:
# Original solution
n, x, m = list(map(int, input().split()))
arr = [x]
mod = x

def find_value(lst, value):
    return [i for i, x in enumerate(lst) if x == value]

ans = 0
for i in range(n-1):
    mod = mod ** 2 % m
    res = find_value(arr, mod)

    if res: 
        j = res[0]
        a = i + 1 - j
        q, mod = divmod((n - j), a)
        ans = sum(arr[0:j]) + q * sum(arr[j:j+a]) + sum(arr[j:j+mod])
        break
    arr.append(mod)

if ans == 0:
    ans = sum(arr)

print(ans)

# Optimized solution
n, x, m = list(map(int, input().split()))
arr = [x]
mod = x
memo = [-1 for _ in range(m+1)]

ans = 0
for i in range(1, n):
    mod = mod ** 2 % m
    idx = memo[mod]

    if idx != -1:
        a = i - idx
        q, _mod = divmod((n - idx), a)

        ans = sum(arr[0:idx]) + q * sum(arr[idx:idx+a]) + sum(arr[idx:idx+_mod])
        break
    arr.append(mod)
    memo[mod] = i

if ans == 0:
    ans = sum(arr)

print(ans)
# Original solution
n,x,m = list(map(int, input().split()))

amari = [x]
cnt = 0
p = 0

for i in range(n-1):
	a = amari[-1]**2 % m
	if a in amari:
		p = amari.index(a)
		cnt = i+1-p
		break
	else:
		amari.append(a)

if cnt == 0:
	print((sum(amari)))
	
else:
	n -= len(amari)
	a = n // cnt
	b = n % cnt
	print((sum(amari)+a*sum(amari[p:])+sum(amari[p:(p+b)])))

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

amari = [x]
amariset = {x}
cnt = 0
p = 0

for i in range(n-1):
	a = amari[-1]**2 % m
	if a in amariset:
		p = amari.index(a)
		cnt = i+1-p
		break
	else:
		amari.append(a)
		amariset.add(a)

if cnt == 0:
	print((sum(amari)))
	
else:
	n -= len(amari)
	a = n // cnt
	b = n % cnt
	print((sum(amari)+a*sum(amari[p:])+sum(amari[p:(p+b)])))
# Original solution
N, X, M = list(map(int, input().split()))

used = [0] * M
a = []

A = X
for i in range(N):
    if used[A] != 0:
        break
    used[A] = 1
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
j = i

if a[-1] != 0:
    result = sum(a[:j])
    a = a[j:]
    l = len(a)
    x = (N - j) // l
    y = (N - j) - x * l
    s = sum(a)
    result += s * x
    result += sum(a[:y])
    print(result)
else:
    s = sum(a)
    print(s)


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

existence = [0] * M
a = []
A = X
for i in range(N):
    if existence[A] != 0:
        break
    existence[A] = 1
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
j = i

result = sum(a[:j])
a = a[j:]
N -= j
x = N // len(a)
y = N % len(a)
result += sum(a) * x + sum(a[:y])
print(result)
# Original solution
N, X, M = list(map(int, input().split()))

existence = [False] * M
a = []
A = X
for i in range(N):
    if existence[A]:
        break
    existence[A] = True
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
loop_start = i

result = sum(a[:loop_start])
a = a[loop_start:]
N -= loop_start
loops = N // len(a)
remainder = N % len(a)
result += sum(a) * loops + sum(a[:remainder])
print(result)


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

existence = [False] * M
a = []
A = X
for i in range(N):
    if existence[A]:
        break
    existence[A] = True
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        loop_start = i
        break
else:
    loop_start = len(a)

result = sum(a[:loop_start])
a = a[loop_start:]
N -= loop_start
if N != 0:
    loops = N // len(a)
    remainder = N % len(a)
    result += sum(a) * loops + sum(a[:remainder])
print(result)
# Original solution
N, X, M = list(map(int, input().split()))

existence = [False] * M
a = []
A = X
for i in range(N):
    if existence[A]:
        break
    existence[A] = True
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        loop_start = i
        break
else:
    loop_start = len(a)

result = sum(a[:loop_start])
N -= loop_start
if N != 0:
    a = a[loop_start:]
    loops = N // len(a)
    remainder = N % len(a)
    result += sum(a) * loops + sum(a[:remainder])
print(result)


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

existence = [False] * M
a = []
A = X
for i in range(N):
    if existence[A]:
        break
    existence[A] = True
    a.append(A)
    A = A * A % M

try:
    loop_start = a.index(A)
except:
    loop_start = len(a)

result = sum(a[:loop_start])
N -= loop_start
if N != 0:
    a = a[loop_start:]
    loops = N // len(a)
    remainder = N % len(a)
    result += sum(a) * loops + sum(a[:remainder])
print(result)
# Original solution
n,x,m = list(map(int, input().split())) 
ans = 0
x_list = []

for _ in range(n):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        ans = sum(x_list)
        break
    if x == 1:
        ans = sum(x_list) + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = sum(x_list) * (n // len(x_list))
            else:
                ans = sum(x_list) * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = sum(after_list) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

# Optimized solution
N, X, M = list(map(int, input().split()))
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)
# Original solution
n,x,m = list(map(int, input().split())) 
ans = 0
x_list = []

for _ in range(min(10**5,n)):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

# Optimized solution
N,x,M=list(map(int,input().split()))
k=x
L=list()
c=dict()
for i in range(M):
  if i==N:
    print((sum(L)))
    exit()
  if x==0:
    print((sum(L)))
    exit()
  L.append(x)
  x=(x*x)%M
  if x in c:
    q=x
    break
  c[x]=1
moto=sum(L)
N-=len(L)
for i in range(len(L)):
  if L[i]==q:
    roop=list(L[i:])
L=roop
a=len(L)
if N%a==0:
  print((moto+(sum(L)*(N//a))))
else:
  s=N//a
  t=N%a
  ans=sum(L)*s
  ans+=sum(roop[:t])
  print((moto+ans))
# Original solution
def f(x, m):
    return (x ** 2) % m


def main():
    n, x, m = list(map(int, input().split()))
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]
    loop = 0

    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break
    if loop == 0:
        print((sum(res[:n])))
        exit()
    ans = sum(res[:non_loop])
    ans += (n - non_loop) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop:non_loop + (n - non_loop) % loop])
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    n, x, m = list(map(int, input().split()))
    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか
    res = []  # 数列A

    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する
        if idx[x] == -1:  # 初めて
            idx[x] = i
            res.append(x)
        else:  # 既出（ループ発見）
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break
        x = (x ** 2) % m

    if n <= len_head + len_loop:  # 1ループ目までで出力する場合
        print((sum(res[:n])))
    else:
        ans = sum(res[:len_head])  # ループ前
        ans += (n - len_head) // len_loop * sum(res[len_head:])  # ループ
        ans += sum(res[len_head: len_head + (n - len_head) %
                       len_loop])  # ループ後の余り
        print(ans)


if __name__ == "__main__":
    main()
# Original solution
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
    p = start
    for _ in range(L):
        front.append(p)
        p = lift(p)
    if L != N:
        for _ in range(L,R):
            cycle.append(p)
            p = lift(p)
        for _ in range(N-(N-L)%period,N):
            end.append(p)
            p = lift(p)
        cnt = (N-L)//period
    return front, cycle, end, cnt

def lift(x): return pow(x,2,M)

################################################################################
import sys
input = sys.stdin.readline

N, X, M = list(map(int, input().split()))
front, cycle, end, cnt = cycle_getter(N,X)
print((sum(front)+sum(cycle)*cnt+sum(end)))

# Optimized solution
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    P = [p]
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
        P.append(p)
    front = P[:L]
    if L != N:
        cycle, end = P[L:R], P[L:L+(N-L)%period]
        cnt = (N-L)//period
    return front, cycle, end, cnt

################################################################################


import sys
input = sys.stdin.readline

def lift(x): return pow(x,2,M)

N, X, M = list(map(int, input().split()))
front, cycle, end, cnt = cycle_getter(N,X)
# print(front, cycle, end, cnt)
print((sum(front)+sum(cycle)*cnt+sum(end)))
# Original solution
# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理


def f(x: int, m: int) -> int:
    return x**2 % m


A = [X]
loop_start_index = 0
while True:
    A_next = f(A[-1], M)
    if A_next in A:
        loop_start_index = A.index(A_next)
        break
    else:
        A.append(A_next)

loop_length = len(A) - loop_start_index
loop_cnt = (N - loop_start_index) // loop_length
loop_res = (N - loop_start_index) % loop_length
ans = sum(A[:loop_start_index]) + loop_cnt * sum(A[loop_start_index:]
                                                 ) + sum(A[loop_start_index: loop_start_index + loop_res])

# 結果出力
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理


def f(x: int, m: int) -> int:
    return x**2 % m


A = [X]
s = {X}
i = 0
while True:
    A_next = f(A[-1], M)
    if A_next in s:
        i = A.index(A_next)
        break
    else:
        A.append(A_next)
        s.add(A_next)

loop_length = len(A) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])

# 結果出力
print(ans)
# Original solution
n,x,m = list(map(int,input().split()))
#listを2つ使って初項からループ手前までのセット、そして二回目のループのセット。
k_1 = list()
k_2 = list()
#len(k_2)でも良かった
#loop_sumはk_2によって表されるループの和
loop_number = 0
loop_sum = 0
while x not in k_1:
	k_1.append(x)
	x = x*x%m
while x not in k_2:
	k_2.append(x)
	loop_number+=1
	loop_sum+=x 
	x = x*x%m
ans = 0
for i in range(len(k_1)):
	ans +=  k_1[i]
ans = ans + loop_sum * ((n-len(k_1))//loop_number)
for i in range((n-len(k_1))%loop_number):
	ans += k_2[i]
print(ans)

# Optimized solution
n,x,m = list(map(int,input().split()))
k_1 = set()
k_2 = set()
tmp = list()
loop_number = 0
loop_sum = 0
while x not in k_1:
	k_1.add(x)
	x = x*x%m
while x not in k_2:
	k_2.add(x)
	tmp.append(x)
	loop_number+=1
	loop_sum+=x 
	x = x*x%m
ans = 0
k_1 = list(k_1)
for i in range(len(k_1)):
	ans +=  k_1[i]
ans = ans + loop_sum * ((n-len(k_1))//loop_number)
for i in range((n-len(k_1))%loop_number):
	ans += tmp[i]
print(ans)
# Original solution
n, x, m = list(map(int, input().split()))
ans = 0
if x == 0:
    print((0))
    exit()
elif x == 1:
    print(n)
    exit()

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)


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

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)
# Original solution
n,x,m=list(map(int,input().split()))
A=[x]
ans=0
for i in range(min(n,m)):
  a_i=(A[i]**2)%m
  if i ==n-1:
    print((sum(A)))
    exit()
  if a_i==0:
    print((sum(A)))
    exit()
  if a_i in A:
    k=A.index(a_i)+1
    l=len(A)
    roop=A[k-1:l]
    many=(n-k+1)//(l-k+1)
    ans+=sum(A[:k-1])
    ans+=sum(roop)*many
    ans+=sum(roop[:(n-k+1)%(l-k+1)])
    print(ans)
    exit()
  A.append(a_i)

# Optimized solution
N, X, M = list(map(int, input().split()))
flag = [False for _ in range(M)]
record = list()
record.append(X)
flag[X] = 1

An = X

for i in range(M + 1):
    An = pow(An, 2, M)
    if flag[An]:
        start = flag[An]
        cnt = i + 2 - start
        cost = record[-1] - record[start - 2] if start > 1 else record[-1]
        break

    else:
        record.append(An + record[-1])
        flag[An] = i + 2

if start >= N:
    print((record[N - 1]))
else:
    print((((N - start) // cnt) * cost
                + record[(N - start) % cnt + start - 1]))
# Original solution
n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
l=len(b)
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)
    


# Optimized solution
n,x,m= list(map(int, input().strip().split()))
t=0
b=[]
b.append(x)
for i in range(m+1):
        if b[-1]**2%m in b:
            b.append(b[-1]**2%m)
            break
        else:
            b.append(b[-1]**2%m)
        
l=len(b) 
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)
# Original solution
N, X, M = [int(x) for x in input().split()]

seen = set()
front = []
cycle = []
for i in range(N):
    x = pow(X, 2 ** i, M)
    if x in seen:
        index = front.index(x)
        front, cycle = front[:index], front[index:]
        break
    front.append(x)
    seen.add(x)


if N <= len(front):
    print((sum(front[:N])))
    exit()

if N <= len(front) + len(cycle):
    print((sum(front) + sum(cycle[: N - len(front)])))
    exit()

q, r = divmod(N - len(front), len(cycle))

if False:
    A = [pow(X, 2 ** i, M) for i in range(N)]
    B = front + cycle * q + cycle[:r]
    print((A, B))
    assert A == B
print((sum(front) + sum(cycle) * q + sum(cycle[:r])))


# Optimized solution
def solve(N, X, M):
    seen = set()
    front = [X]
    cycle = []
    for i in range(N - 1):
        x = (front[-1] * front[-1]) % M
        if x in seen:  # seen can't be more than M since x is < M
            index = front.index(x)
            front, cycle = front[:index], front[index:]
            break
        front.append(x)
        seen.add(x)
    if N <= len(front):
        return sum(front[:N])

    if N <= len(front) + len(cycle):
        return sum(front) + sum(cycle[: N - len(front)])

    q, r = divmod(N - len(front), len(cycle))

    if False:
        A = [pow(X, 2 ** i, M) for i in range(N)]
        B = front + cycle * q + cycle[:r]
        print((A, B))
        assert A == B
    return sum(front) + sum(cycle) * q + sum(cycle[:r])


N, X, M = [int(x) for x in input().split()]
print((solve(N, X, M)))
# Original solution
N,X,M = list(map(int,input().split()))

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
    else:
        val.add(data[i])

if N<=M:
    print((sum(data[:N])))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)

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

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
        break
    else:
        val.add(data[i])

if N<=M:
    print((sum(data[:N])))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)
# Original solution
N,X,M = list(map(int,input().split()))
count = 1
S = X
A = [X]

for i in range(2,N+1):
  A_i = (A[-1]*A[-1])%M
  A.append(A_i)
  S += A_i
  if len(A) != len(set(A)):
    S -= A_i
    del A[-1]
    B = A[A.index(A_i):]
    S += ((N-len(A))//len(B))*sum(B) + sum(B[:((N-len(A))%len(B))])
    break

print(S)

# Optimized solution
N,X,M = list(map(int,input().split()))
S = X
A = [X]
exists = [0]*M
exists[X] = 1

for i in range(2,N+1):
  A_i = (A[-1]*A[-1])%M
  A.append(A_i)
  S += A_i
  if exists[A_i] == 0:
    exists[A_i] = 1
  else:
    S -= A_i
    del A[-1]
    B = A[A.index(A_i):]
    S += ((N-len(A))//len(B))*sum(B) + sum(B[:((N-len(A))%len(B))])
    break

print(S)
# Original solution
n, x, m = [int(_) for _ in input().split()]
d = {}
d_rev = {}
d[x] = 0
d_rev[0] = x
c = 0
while True:
    c += 1
    x = (x ** 2) % m
    if x in d:
        roop_idx = d[x]
        break
    else:
        d[x] = c
        d_rev[c] = x
# print(d)
# print(d_rev)

ans = 0
if roop_idx >= n:
    for i in range(n):
        ans += d_rev[i]
    print(ans)
else:
    for i in range(roop_idx):
        ans += d_rev[i]
    roop_num = len(d) - roop_idx
    roop_sum = 0
    for i in range(roop_idx, len(d)):
        roop_sum += d_rev[i]
    ans += ((n-roop_idx)//roop_num) * roop_sum
    roop_last = (n-roop_idx)%roop_num
    for i in range(roop_last):
        ans += d_rev[roop_idx + i]
    print(ans)

# Optimized solution
n, x, m = [int(_) for _ in input().split()]
d = {}
d_rev = {}
d[x] = 0
d_rev[0] = x
c = 0
while True:
    c += 1
    x = (x ** 2) % m
    if x in d:
        roop_idx = d[x]
        break
    else:
        d[x] = c
        d_rev[c] = x

ans = 0
if roop_idx >= n:
    for i in range(n):
        ans += d_rev[i]
    print(ans)
else:
    for i in range(roop_idx):
        ans += d_rev[i]
    roop_num = len(d) - roop_idx
    roop_sum = 0
    for i in range(roop_idx, len(d)):
        roop_sum += d_rev[i]
    ans += ((n-roop_idx)//roop_num) * roop_sum
    roop_last = (n-roop_idx)%roop_num
    for i in range(roop_last):
        ans += d_rev[roop_idx + i]
    print(ans)
# Original solution
n, x, m = list(map(int, input().split()))

mn = min(n, m)
S = set()
A = []
a = x
ans = 0

for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()

if len(A) >= mn:
    print(ans)
    exit()

st_len = 0
while st_len < len(A) and a != A[st_len]: st_len += 1
st = sum(A[:st_len])
cyc_sum = sum(A[st_len:])
cyc_len = len(A) - st_len
cyc_num = (n - st_len) // cyc_len
cyc = cyc_sum * cyc_num
ed_len = (n - st_len) % cyc_len
ed = sum(A[st_len:][:ed_len])
print((st + cyc + ed))


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

mn = min(n, m)
S = set()
A = []
a = x
sum_9 = 0 # sum of pre + cycle

for _ in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    sum_9 += a
    a = a*a % m
    if a == 0:
        print(sum_9)
        exit()

if len(A) >= mn:
    print(sum_9)
    exit()

st_len = A.index(a)
cyc_len = len(A) - st_len
ed_len = (n - st_len) % cyc_len

cyc_num = (n - st_len) // cyc_len

pre = sum(A[:st_len])
cyc = sum_9 - pre
btm = sum(A[st_len: st_len + ed_len])

print((pre + cyc * cyc_num + btm))
# 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 = [False] * m # for cycle check
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        cyc = sum(P[pre_len:]) * ((n - pre_len) // cyc_len)
        remain = sum(P[:pre_len + nxt_len])
        print((cyc + remain))
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)


# Optimized 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 = [False] * m # for cycle check
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        pre = sum(P[:pre_len])
        cyc = (sum_p - pre) * ((n - pre_len) // cyc_len)
        nxt = sum(P[pre_len: pre_len + nxt_len])
        print((pre + cyc + nxt))
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)