#!/usr/bin python3

# -*- coding: utf-8 -*-



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



s = set([])

v = []

for i in range(m+1):

    s.add(x)

    v.append(x)

    x = pow(x,2,m)

    if x in s:

        break

st = v.index(x)

lp = len(v)-st

lps = sum(v[st:])



k = (n-(st+lp)+(lp-1))//lp

ret = lps * k

n -= lp * k

ret += sum(v[:n])



print(ret)
#!/usr/bin python3

# -*- coding: utf-8 -*-



# ループを検索して計算量圧縮

# 0->1->...->st->st+1->...->st+lp-1-┐

#             └─────────────────────┘

#                       lp





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



seen = set([])

seqs = []

for i in range(m+1):

    seen.add(x)

    seqs.append(x)

    x = pow(x,2,m)

    if x in seen:

        break

start = seqs.index(x)

lp = len(seqs) - start



lpsum = sum(seqs[start:])

lptimes = (n-(start+lp)+(lp-1))//lp

ret_sum = lpsum * lptimes

n -= lp * lptimes

ret_sum += sum(seqs[:n])

ret_val = seqs[n-1]



print(ret_sum)

#print(ret_val)
#!/usr/bin python3
# -*- coding: utf-8 -*-
n, x, m = list(map(int, input().split()))
s = set([])
v = []
for i in range(m + 1):
    s.add(x)
    v.append(x)
    x = pow(x, 2, m)
    if x in s:
        break
st = v.index(x)
lp = len(v) - st
lps = sum(v[st:])
k = (n - (st + lp) + (lp - 1)) // lp
ret = lps * k
n -= lp * k
ret += sum(v[:n])
print(ret)

#!/usr/bin python3
# -*- coding: utf-8 -*-
# ループを検索して計算量圧縮
# 0->1->...->st->st+1->...->st+lp-1-┐
#             └─────────────────────┘
#                       lp
n, x, m = list(map(int, input().split()))
seen = set([])
seqs = []
for i in range(m + 1):
    seen.add(x)
    seqs.append(x)
    x = pow(x, 2, m)
    if x in seen:
        break
start = seqs.index(x)
lp = len(seqs) - start
lpsum = sum(seqs[start:])
lptimes = (n - (start + lp) + (lp - 1)) // lp
ret_sum = lpsum * lptimes
n -= lp * lptimes
ret_sum += sum(seqs[:n])
ret_val = seqs[n - 1]
print(ret_sum)
# print(ret_val)

+# ループを検索して計算量圧縮 +# 0->1->...->st->st+1->...->st+lp-1-┐ +#             └─────────────────────┘ +#                       lp -s = set([]) -v = [] +seen = set([]) +seqs = [] -    s.add(x) -    v.append(x) +    seen.add(x) +    seqs.append(x) -    if x in s: +    if x in seen: -st = v.index(x) -lp = len(v) - st -lps = sum(v[st:]) -k = (n - (st + lp) + (lp - 1)) // lp -ret = lps * k -n -= lp * k -ret += sum(v[:n]) -print(ret) +start = seqs.index(x) +lp = len(seqs) - start +lpsum = sum(seqs[start:]) +lptimes = (n - (start + lp) + (lp - 1)) // lp +ret_sum = lpsum * lptimes +n -= lp * lptimes +ret_sum += sum(seqs[:n]) +ret_val = seqs[n - 1] +print(ret_sum) +# print(ret_val)