Let us denote by f(x, m) the remainder of the Euclidean division of x by m.
Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

-----Constraints-----
 - 1 \leq N \leq 10^{10}
 - 0 \leq X < M \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X M

-----Output-----
Print \displaystyle{\sum_{i=1}^N A_i}.

-----Sample Input-----
6 2 1001

-----Sample Output-----
1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Difficulty: interview

Starter code:

Solutions:
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations
N, X, M = list(map(int, input().split()))

# X^2がMより大きい場合はMで割った余り、小さければそのままを返却
def f(X, M):
    if X**2 >= M:
        return X**2 % M
    else:
        return X**2

appear = np.full(M, -1)
seq = []
fx = X
appear[fx] = 0
seq.append(fx)
for i in range(1, N):
    fx = f(fx, M)
#     print(fx, appear[fx])
    if appear[fx] != -1:
        loop_st = appear[fx]
        loop_en = i
        break
    seq.append(fx)
    appear[fx] = i
seq.insert(0, 0)
seq_sum = np.cumsum(seq)

if N <= len(seq)-1 :
    print((seq_sum[N]))
else:
    # ループの前まで
    lp_b = seq_sum[loop_st-1]
    # ループしている個数を求める
    loop_num = (len(seq_sum)-1) - loop_st
    # 商はループ回数、余りはループしきらなかった分
    qu = (N-(loop_st)) // loop_num
    mo = (N-(loop_st)) % loop_num
    # ループした分だけかける
    lp_sum = (seq_sum[-1] - seq_sum[loop_st]) * qu
    # 最後の余りの部分を加算
    lp_en = seq_sum[loop_st+mo] - seq_sum[loop_st-1]
    print((lp_b+lp_sum+lp_en))
    


n,x,m=map(int,input().split())
used=[0]*m
used[x]=1
l=[x]
while True:
    x=x**2%m
    if used[x]==1:
        break
    else:
        used[x]=1
        l.append(x)
a=len(l)
for i in range(a):
    if l[i]==x:
        b=i
        break
c=a-b
s=sum(l[b:])
s_=sum(l[:b])
if n<b:
    print(sum(l[:n]))
else:
    print(s_+s*((n-b)//c)+sum(l[b:b+(n-b)%c]))

import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N, X, M = list(map(int, input().strip().split()))
    return N, X, M


def solve(N, X, M):
    # log2(10**10) ~ 33.2
    D = 34
    A = [[0 for j in range(M)] for i in range(D)]
    S = [[0 for j in range(M)] for i in range(D)]
    
    for j in range(M):
        # A[0][j] := 0ステップ目がjであるときの、2^0=1ステップ先の値
        A[0][j] = j * j % M
        # S[0][j] := jの2^0=1ステップ目までの総和
        S[0][j] = j
    for i in range(0, D-1):
        for j in range(M):
            # A[i][j] := 0ステップ目がjであるときの、2^iステップ先の値
            A[i+1][j] = A[i][A[i][j]]
            S[i+1][j] = S[i][j] + S[i][A[i][j]]
    ans = 0
    x = X
    for i in range(D-1, -1, -1):
        if N & (1 << i) == (1 << i):
            ans += S[i][x]
            x = A[i][x]
    return ans


def __starting_point():
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print(("%s" % str(outputs)))

__starting_point()

n, x, m = map(int, input().split())
a = []
mp = dict()
cnt, tot = 0, 0
while mp.get(x, -1) == -1:
    a.append(x)
    tot += x
    mp[x] = cnt
    cnt += 1
    x = (x * x) % m

if n <= cnt:
    ans = 0
    for i in range(0, n): ans += a[i]
    print(ans)
    return
cycle = 0
rest = cnt - mp.get(x, 0)
for i in range(mp[x], cnt):
    cycle += a[i]
n-= cnt
ans = tot
ans += (n // rest) * cycle
n %= rest
si = mp.get(x, 0)
for i in range(n): ans += a[si + i]
print(int(ans))

n, x, m = map(int, input().split())
d = [0]*(m+1)
tmp = x
check = [tmp]
while d[tmp] == 0:
    d[tmp] = 1
    tmp = (tmp**2)%m
    check.append(tmp)
for i in range(len(check)):
    if check[i] == check[-1]:
        index = i
        break
sum_c = sum(check[index:len(check)-1])
cycle = (n - index) // (len(check)-index-1)
rest = n - index - cycle*(len(check)-index-1)
print(sum(check[:index+rest])+sum_c*cycle)

n, x, m = map(int, input().split())
if m >= n:
    ans = 0
    for i in range(n):
        ans += x
        x **= 2
        x %= m
    print(ans)
    return
l = [x]
d = {}
for i in range(m):
    d[i] = 0
d[x] += 1
for i in range(m):
    x = (x**2)%m
    if d[x] == 1:
        y = l.index(x)
        print(sum(l[:y])+sum(l[y:])*((n-y)//(len(l)-y))+sum(l[y:][:(n-y)%(len(l)-y)]))
        return
    l.append(x)
    d[x] += 1

# 繰り返しの始まり + 繰り返し + 途中で終わった繰り返し分
N,X,M = map(int,input().split())
p = [0] * (M+2)
sum = [0] * (M+2)
p[X] = 1
sum[1] = X

repeat_start = 0
repeat_end = 0

for i in range(2,N+1):
  X = (X**2) % M
  if p[X] != 0:
    repeat_start = p[X]
    repeat_end = i
    break
  else:
    sum[i] = sum[i-1] + X
    p[X] += i

if repeat_start == 0:
  print(sum[N])
else:
  repeat_cnt,mod=divmod(N-repeat_start+1,repeat_end-repeat_start)
  print(repeat_cnt*(sum[repeat_end-1]-sum[repeat_start-1]) + sum[repeat_start+mod-1])

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

idx = [-1] * M
A = []
total = 0
length = 0

while idx[X] == -1:
    A.append(X)
    idx[X] = length
    length += 1
    total += X
    X = pow(X, 2, M)

cycle = length - idx[X]
cycle_sum = sum(A[idx[X]:length])

ans = 0
if length >= N:
    print((sum(A[:N])))
else:
    ans += total
    N -= length
    l, m = divmod(N, cycle)
    ans += cycle_sum * l
    ans += sum(A[idx[X]:idx[X] + m])
    print(ans)


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

A = [X]
item = set()
for i in range(N-1):
    next = (A[i] ** 2) % M
    if next in item:
        loop_start = A.index(next)
        loop_length = len(A) - loop_start
        loop_times = (N - loop_start) // loop_length
        loop_remain = (N - loop_start) % loop_length
        cnt = sum(A[:loop_start]) + (sum(A[loop_start:]) * loop_times) + sum(A[loop_start:loop_start + loop_remain])
        print(cnt)
        return
    A.append(next)
    item.add(next)
print((sum(A)))


import sys

# import numpy as np
# from numba import njit
#
# read = sys.stdin.read
readline = sys.stdin.readline


# readlines = sys.stdin.readlines


def solve(n, x, m):
    a = [x]
    a_set = {x}
    ai = x
    for _ in range(m):
        ai = ai ** 2 % m
        if ai in a_set:
            start = a.index(ai)
            loop = a[start:]
            lall = len(a)
            lloop = len(loop)
            break
        else:
            a.append(ai)
            a_set.add(ai)

    if n - 1 <= lall:
        ans = sum(a[:n])
    else:
        q, r = divmod(n - lall, lloop)
        ans = sum(a) + sum(loop) * q + sum(loop[:r])

    return ans


n, x, m = map(int, readline().split())
print(solve(n, x, m))

n, x, m = list(map(int, input().split()))
A = []
ls = [0] * (m+1) 
start = 0
cycle_sum = 0
cnt = 0
while ls[x] == 0:
    A.append(x)
    cycle_sum += x
    ls[x] = cnt
    cnt += 1
    x = (x*x) % m 

if n <= cnt :
    ans = 0
    for i in range(0, n): ans += A[i]
    print(ans)
    return
cycle = 0
rest = cnt - ls[x]
for i in range(ls[x], cnt):
    cycle += A[i]
n -= cnt 
ans = cycle_sum
ans += (n//rest) * cycle 
n %= rest
si = ls[x]
for i in range(n):
    ans += A[si + i]
print(ans)


n, x, m = map(int, input().split())
mod = [-1] * m
start = 0
end = 0
a = [x]
mod[x] = 0
for i in range(1, m):
  if i >= n:
    break
  a_new = a[-1]**2 % m
  if mod[a_new] == -1:
    mod[a_new] = i
  else:
    start = mod[a_new]
    end = i
    break
  a.append(a_new)

loop_num = 0
last_num = 0
if end - start:
  loop_num = (n - start) // (end - start)
  last_num = (n - start) % (end - start)
  out = sum(a[:start]) + sum(a[start:end + 1]) * loop_num
  out += sum(a[start:start+last_num])
else:
  out = sum(a)

print(out)

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

a_idx = [-1] * m
a_idx[x] = 0
a = [x]
idx = 1
while True:
    y = (a[-1]**2) % m
    if a_idx[y] != -1:
        i = a_idx[y]
        j = len(a) - i
        break
    else:
        a_idx[y] = idx
        idx += 1
        a.append(y)

ans = sum(a) * (n)
ans = sum(a[:i]) + sum(a[i:]) * ((n - i) // j) + sum(a[i:i + (n - i) % j])
print(ans)


N,X,M=map(int,input().split())
ans=0
A=[]
sa=set(A)
while N:
    if X not in sa:
        ans+=X
        A.append(X)
        sa.add(X)
        X=X**2%M
        N-=1
    else:
        i=A.index(X)
        B=A[i:]
        L=len(B)
        ans+=sum(B)*(N//L)+sum(B[:N%L])
        N=0
print(ans)

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

A = [-1, X]
pre = X
sums = [-1, X]
presum = X

for _ in range(M + 1):
    pre = (pre * pre) % M
    A.append(pre)

    presum += pre
    sums.append(presum)

if N <= M:
    print(sums[N])
    return

lstart = M + 1

while A[lstart] != pre:
    lstart -= 1

loopsum = sums[-1] - sums[lstart]

looplen = M + 2 - lstart
loopcnt = (N - lstart) // looplen
over = (N - lstart) % looplen

ans = loopsum * loopcnt + sums[lstart + over]

print(ans)

import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,x,md=MI()
# n,x,md=6,7,13
pos=[-1]*md
aa=[]
if x==0:
    print(0)
    return

for i in range(md):
    if pos[x]!=-1:
        p=pos[x]
        c=i-pos[x]
        # print(x,i,pos[x])
        break
    aa.append(x)
    pos[x]=i
    x=pow(x,2,md)
cs=sum(aa[p:])

# print(p,c)
# print(pos)
# print(aa)

if n<=len(aa):
    print(sum(aa[:n]))
    return

n-=p
cnt=n//c
n%=c
n+=p
print(cs*cnt+sum(aa[:n]))


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

a = X
path = [a]
done = set([a])
while True:
    na = pow(a,2,M)
    if na in done:
        s = path.index(na)
        break
    else:
        path.append(na)
        done.add(na)
        a = na

if N < s +1:
    ans = sum(path[:N])
else:
    rest = N - s
    x,y = divmod(rest,len(path)-s)
    ans = sum(path[:s])
    ans += sum(path[s:])*x
    ans += sum(path[s: s+y])
print(ans)


def main():
    n,x,m = list(map(int,input().split()))
    ans = x
    now = x
    used = [0] * (m + 1)
    used[now] = 1
    cnt = 1
    while True:
        if cnt == n:
            print(ans)
            return
        cnt += 1
        now = (now ** 2) % m
        if used[now] > 0:
            break
        used[now] = cnt
        ans += now
    start = used[now]


    ans = 0
    now = x
    cycle = 0
    startNum = 0
    for i in range(1, cnt):
        if i < start:
            ans += now
        elif i == start:
            cycle += now
            startNum = now
        else:
            cycle += now
        now = (now ** 2) % m
    rem = n - start + 1
    cycleCnt = cnt - start
    roopCnt = rem // cycleCnt
    ans += roopCnt * cycle
    now = startNum
    for i in range(roopCnt * cycleCnt + start, n+1):
        ans += now
        now = (now ** 2) % m
    print(ans)
def __starting_point():
    main()

__starting_point()

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

def calc(n, x, m):
    nxt = lambda y: y**2%m

    y = x
    r = n
    l = [0]*m
    for i in range(1, n+1):
        if l[y]:
            r = i-l[y]
            break
        l[y] = i
        y = nxt(y)
    else: return sum(i for i, v in enumerate(l) if v)

    ans = 0
    for i in range(i):
        ans += x
        x = nxt(x)
    n -= i+1
    for i in range(r):
        ans += x*(n//r)
        x = nxt(x)
    for i in range(n%r):
        ans += x
        x = nxt(x)

    return ans

print(calc(N, X, M))

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

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

a_list = [x]
a = x
i = 1
while (i<n and i < m+1):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

print(ans)

[N, X, M] = [int(i) for i in input().split()]
L = [X]
ans = X
dic = {}
for i in range(1, N):
    t = (L[-1]**2)%M
    if t in dic:
        x = dic[t]
        ans += (sum(L[x:i+1])) * ((N-i)//(i-x)) + sum(L[x:x+(N-i)%(i-x)])
        break
    else:
        L.append(t)
        dic[t] = i
        ans += t
 
print(ans)

n, x, m = list(map(int, input().split()))
X = [-1] * m
P = []
sum_p = 0
while X[x] < 0: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
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))


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

visit = [-1] * m
a_sum = [0] *(m+1)

a = x
a_sum[1] = x
visit[a] +=1

flg = True

if n == 1:
    print(x)
    return
if x == 0:
    print((0))
    return

for i in range(1,n):
    a = (a**2)%m
    a_sum[i+1] = a_sum[i] + a
    if visit[a] == -1:
        visit[a] = i
    else:
        li = visit[a] 
        roop = i - li
        roop_sum = a_sum[i]-a_sum[li]
        flg = False
        break

if flg:
    print((a_sum[i+1]))
    return

sum = a_sum[li] 
sum += roop_sum*((n-li)//roop)
sum += a_sum[li + (n-li)%roop] - a_sum[li]

print(sum)







n, x, m = list(map(int, input().split()))
x %= m
d = {x:1}
arr = [0] * (m+1)
arr[1] = x
for i in range(2, n+1):
    x = (x * x) % m
    if x in d:
        start = d[x]
        end = i - 1
        sumPreCycle = sum(arr[1:start])
        numPreCycle = start - 1
        lenCycle = end - start + 1
        sumCycle = sum(arr[start:end+1])
        numCycle = (n - numPreCycle) // lenCycle
        numAfterCycle = n - numPreCycle - lenCycle * numCycle
        sumAfterCycle = sum(arr[start:start+numAfterCycle])
        print((sumPreCycle + sumAfterCycle + sumCycle * numCycle))
        break
    else:
        arr[i] = x
        d[x] = i
else:
    print((sum(arr[1:n+1])))


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

step = [0 for i in range(M)]
sums = [i for i in range(M)]

for i in range(len(step)):
  step[i] = i ** 2 % M
  
ans = 0
while N:
  if N & 1:
    ans += sums[X]
    X = step[X]
  sums = [sums[i] + sums[step[i]] for i in range(M)]
  step = [step[step[i]] for i in range(M)]
  N >>= 1
  
print(ans)

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
x_table=[0 for i in range(m+1)]
x_table[x]=1

for i in range(1,n):
  x=(x**2)%m

  if x_table[x]!=0:
    inx=x_list.index(x)
    loop=x_list[inx:]
    zan=n-i

    p=zan//len(loop)
    q=zan%len(loop)

    ans+=sum(loop)*p
    ans+=sum(loop[:q])

    break

  else:
    ans+=x
    x_list.append(x)
    x_table[x]+=1

print(ans)

n, x, m = list(map(int, input().split()))
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
P.append(sum_p) # full sum_p
p_len = len(P) - 1
cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print((cyc + remain))


n, x, m = list(map(int, input().split()))
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
P.append(sum_p) # full sum_p

p_len = len(P) - 1
if n <= p_len:
    print((P[n])) # sum_p
    return

cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print((cyc + remain))


# coding: utf-8


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

    a = x
    ret = 0
    I = [-1]*(m+1)
    A = []

    for i in range(n):
        if I[a] < 0:
            I[a] = i
            A.append(a)
            ret += a
        else:
            A = A[I[a]:]
            d, r = divmod(n-i-1, len(A))
            ret += (d+1)*sum(A[:r+1])+d*sum(A[r+1:])
            break
        a = pow(a, 2, m)

    return str(ret)


def __starting_point():
    print((solve(*(open(0).read().splitlines()))))

__starting_point()

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

li = [-1 for i in range(M)]
a = []
l = 0
tot = 0
while li[X]==-1:
  a.append(X)
  li[X] = l
  l += 1
  tot += X
  X = (X*X)%M

c = l - li[X]
s = 0
for i in range(li[X],l):
  s += a[i]

ans = 0
if N<=l:
  for i in range(N):
    ans += a[i]
else:
  ans += tot
  N -= l
  ans += s*int(N/c)
  for i in range(N%c):
    ans += a[li[X]+i]
print(ans)

def main():
    n, x, m = list(map(int, input().split()))
    a, r, ans = [0]*(m+1), 0, 0
    chk = [False] * (m+1)
    a[0] = x
    for i in range(m):
        tmp = pow(a[i], 2, m)
        if tmp == 0:
            print((sum(a)))
            return
        r = i+1
        if chk[tmp]:
            l = a.index(tmp)
            ans = sum(a[l:r])*((n-l)//(r-l))
            ans += sum(a[l:l+(n-l) % (r-l)])
            break
        else:
            chk[tmp] = True
        a[r] = tmp
    print((ans+sum(a[:l])))


def __starting_point():
    main()

__starting_point()

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

visit = [0] * m
visit_t = [0] * m
a = [0] *(m+1)
a_sum = [0] *(m+1)

a[1] = x
a_sum[1] = x
visit[a[1]] +=1


flg = True

if n == 1:
    print(x)
    return
if x == 0:
    print((0))
    return

for i in range(1,n):
    a[i+1] = (a[i]**2)%m
    a_sum[i+1] = a_sum[i] + a[i+1]
    if visit[a[i+1]] == 0:
        visit[a[i+1]] += 1
        visit_t[a[i+1]] = i
    else:
        li = visit_t[a[i+1]] 
        roop = i - li
        roop_sum = a_sum[i]-a_sum[li]
        flg = False
        break

if flg:
    print((a_sum[i+1]))
    return

sum = a_sum[li] 
sum += roop_sum*((n-li)//roop)
sum += a_sum[li + (n-li)%roop] - a_sum[li]

print(sum)






N,X,M = map(int,input().split())
id = [-1] * M
a = []
l = 0
total = 0
while(id[X] < 0):
  a.append(X)
  id[X] = l
  total += X
  l += 1
  X = pow(X,2,M)
  
c = l - id[X]
s = 0
for i in range(id[X], l, 1):
  s += a[i]

ans = 0
if N <= c:
  for i in range(N):
    ans += a[i]
else:
  ans += total
  N -= l
  ans += s * (N//c)
  N %= c
  for i in range(N):
    ans += a[id[X] + i]
print(ans)

def main():
  n,x,m = map(int,input().split())
  a = [x]
  at = [x]
  aset = set(a)
  i = 1
  while(True):
    an = a[-1]**2%m
    if an in aset:
      ca = a.index(an)
      break
    a.append(an)
    aset.add(an)
    at.append(at[-1]+a[-1])
    i+=1
    if i == n:
      print(at[-1])
      return
  #aa = a[:ca]
  ata = [0]+at[:ca]
  #ab = a[ca:]
  atb = [ata[-1]]+at[ca:]
  cb = len(atb)-1
  na = min(n,ca)
  nb,nc = divmod(n-na,cb)
  print(ata[na]+(atb[-1]-ata[-1])*nb+atb[nc]-ata[-1])
main()

N,X,M=map(int,input().split())
table=[X]
visited=[-1]*M
visited[X]=1

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if visited[nx]>0:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        return
    else:
        table.append(nx)
        visited[nx]=1
        ans+=nx
 

print(ans)

n, x, m = 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)
        return
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

S = input().split()

N, X, M = [int(s) for s in S]

init = X
count = 0
box = [0] * (M + 2)

for i in range(M):
  box[i] = X
  X = (X ** 2) % M
  
T = len(set(box))

for t in range(T):
  if box[t] == box[T]:
    break
    

print(sum(box[:t]) + ((N - t)//(T - t)) * sum(box[t:T]) + sum(box[t:t + (N - t)%(T - t)]))

N,X,mod=map(int,input().split())
l=[X]
se=set(l)
mem=-1
for i in range(N-1):
   if l[-1]**2%mod in se:
      mem=l[-1]**2%mod
      break
   else:
      c=l[-1]**2%mod
      l.append(c);se.add(c)
if mem==-1:
   print(sum(l))
   return
N-=i+2
ans=sum(l)
index=l.index(mem)
roop=len(l)-index
l=l[index:]
can,rem=divmod(N,roop)
ans+=sum(l)*can
ans+=sum(l[:rem+1])
print(ans)

n,x,m=map(int,input().split());l,k,i,j=[-1]*m,[],0,-1
while j<0:l[x]=i;k+=[x];x=x**2%m;i+=1;j=l[x]
n-=i;r=i-j;print(n//r*sum(k[j:])+sum(k+k[j:n%r+j]))

def main():
    n, x, m = list(map(int, input().split()))
    a, r, l = [0]*(m+1), 0, 0
    chk = [False] * (m+1)
    a[0] = x
    for i in range(m):
        tmp = pow(a[i], 2, m)
        if chk[tmp] or tmp == 0:
            if tmp == 0:
                print((sum(a)))
                return
            r = i+1
            l = a.index(tmp)
            break
        else:
            chk[tmp] = True
        a[i+1] = tmp
    print((sum(a[:l]) + sum(a[l:r])*((n-l)//(r-l)) + sum(a[l:l+(n-l) % (r-l)])))


def __starting_point():
    main()

__starting_point()

N,X,M = list(map(int,input().split()))
#Mでわるので、高々M個の種類しかなく、ループする
#ループ開始のindexを保管していく
dic={}
a = X
dic[X]=1
seen = set([a])
roop_length = 0
roop_start = 0
ans = X
for i in range(2,N+1):
    a = pow(a,2,M)
    if a in seen:
        roop_length = i - dic[a]
        roop_start = dic[a]
        roop_start_a = a

        break
    else:
        ans += a
        seen.add(a)
        dic[a]=i
roop_ans = 0
if roop_length >0:
    roop_ans = roop_start_a
    a = roop_start_a
    for i in range(1,N+1):
        a = pow(a,2,M)
        if a != roop_start_a:
            roop_ans += a
        else:
            break
    roop_ans = roop_ans * ((N-roop_start+1)//roop_length-1)

#ループ後ののこりは？
rest_ans = 0
if roop_length>0:
    rest_num = (N-roop_start+1)%roop_length
    rest_ans = roop_start_a*(rest_num>0)
    a = roop_start_a
    for _ in range(1,rest_num):
        a = pow(a,2,M)
        rest_ans += a
        
ans_all = ans + roop_ans+rest_ans
print(ans_all)
    


import pprint

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


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

def solve1(n: int, x: int, m: int) -> int:
    d = {x: 0}
    A = [x]
    ans = A[0]
    loop_count = 0

    #print("(", A[0], end="")

    for i in range(n):
        A_next = f(A[i]**2, m)

        if A_next in d:
            loop_count = (n - d[A_next] - 1) // (d[A[i]] - d[A_next] + 1)

            mod_left = d[A_next]
            mod_right = mod_left + \
                ((n - d[A_next] - 1) % (d[A[i]] - d[A_next] + 1) + 1)

            #print(" ) + (", A[d[A_next]:A[i]], ") * ", loop_count-1, end="")
            #print(" + (", A[mod_left:mod_right], ")", end="")

            ans += sum(A[d[A_next]:A[i]]) * (loop_count - 1)
            ans += sum(A[mod_left:mod_right])
            break
        else:
            A.append(A_next)
            d[A_next] = i + 1
            ans += A[i+1]
            #print(" +", A[i+1], end="")
    else:
        #print(" )", end="")
        #print(" - ", A[-1], end="")
        ans -= A[-1]

    #print(" =", ans)

    return ans


print((solve1(n, x, m)))


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))
        return
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


#高々Mの繰り返し
N,X,M =list(map(int,input().split()))
memo = [0]*(2*M+1)#最長2Mまでloopするはず
val_idx = {X:1}#loopしたときに、どこがloop開始のインデックスかを知るためのメモ
seen = set([X])#見た判定。o(1)で判定するため
memo[1]=X#累積和を取っておく

loop_length = 0#loopしたか、したならloop長はなにか
for i in range(2,N+1):
    X = (X**2)%M
    if X not in seen:#まだloopしてない
        seen.add(X)
        val_idx[X]=i
        memo[i]+=memo[i-1]+X
    else:#loopした
        loop_start_val = X
        loop_start_idx = val_idx[X]
        loop_length = i-loop_start_idx
        break
if loop_length == 0:#ループしなかったら、N番目
    print((memo[N]))
else:#ループしたなら
    rest_num = (N-loop_start_idx+1)%loop_length#ループの後ろのきれっぱし
    loop_num =(N-loop_start_idx+1)//loop_length#ループ回数
    ans = (memo[loop_start_idx+loop_length-1]-memo[loop_start_idx-1])*loop_num+memo[loop_start_idx-1+rest_num]#1ループの和 x ループ回数＋きれっぱし
    print(ans)


n,x,m = map(int,input().split())
l = [x]
s = {x}
for i in range(n):
    x = x*x % m
    if x in s:
        break
    l += [x]
    s.add(x)
xi = 0
for i in range(len(l)):
    if x == l[i]:
        xi = i
        break
ans = 0
if n <= xi:
    print(sum(l[:n]))
    return
ans = sum(l[:xi])
n -= xi
l = l[xi:]
print(ans + sum(l) * (n // len(l)) + sum(l[:(n%len(l))]))

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


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

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

n_loop = len(A) - i
s, l = A[:i], A[i:]
div, mod = divmod(N - i, n_loop)
print(sum(s) + sum(l) * div + sum(l[:mod]))

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

r = [-1 for _ in range(M)]
a = X
r[a] = 0
p = [a]

# M回繰り返せば，必ずかぶる
for i in range(1, M + 1):
    an = a ** 2 % M
    if r[an] >= 0:
        break
    r[an] = i
    p.append(an)
    a = an

q = p[r[an] :]
p = p[: r[an]]

if N <= len(p):
    ans = sum(p[:N])
else:
    ans = sum(p)
    N -= len(p)
    a, b = divmod(N, len(q))
    ans += a * sum(q)
    ans += sum(q[:b])

print(ans)


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

def calc(n, x, m):
    nxt = lambda y: y**2%m

    y = x
    r = n
    l = [0]*m
    for i in range(1, n+1):
        if l[y]:
            r = i-l[y]
            break
        l[y] = i
        y = nxt(y)

    ans = 0
    for i in range(i):
        ans += x
        x = nxt(x)
    n -= i+1
    for i in range(r):
        ans += x*(n//r)
        x = nxt(x)
    for i in range(n%r):
        ans += x
        x = nxt(x)

    return ans

print(calc(N, X, M))

n, x, m = map(int, input().split())
list_A = [x]
set_A = {x}
while True:
    a = pow(list_A[-1], 2, m)
    if a in set_A:
        break
    list_A.append(a)
    set_A.add(a)

if len(list_A) >= n:
    print(sum(list_A[:n]))
else:
    k = list_A.index(a)
    s = sum(list_A[k:])
    l = len(list_A) - k

    h = (n - len(list_A)) // l
    g = (n - len(list_A)) % l

    ans = sum(list_A) + h * s + sum(list_A[k:k + g])

    print(ans)

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

check=[0]*(m+1)
tmp=x%m
al=[x%m]
check[x%m]=1
while(True):
    tmp=tmp*tmp%m
    al.append(tmp)
    if check[tmp]==0:
        check[tmp]=1
    else:
        break
j=[]
start=0
flag=False
for i in range(len(al)):
    if al[i]==al[-1] and i!=len(al)-1:
        flag=True
        start=i
    if flag:
        if i!=len(al)-1:
            j.append(al[i])

ans=0
for i in range(start):
    ans+=al[i]

p=n-start
ans+=sum(j)*(p//len(j))
y=p%len(j)
for i in range(y):
    ans+=j[i]

print(ans)

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

a = [x]
c = [0]*(m+1)
flag = False
for i in range(1, n):
    v = a[i-1]**2 % m
    if c[v] == 1:
        flag = True
        break
    a.append(v)
    c[v] = 1
if flag:
    e = a.index(v)
    s = len(a) - e
    d, f = divmod(n-e, s)
    print(sum(a[:e]) + d*sum(a[e:e+s]) + sum(a[e:e+f]))
else:
    print(sum(a))

from collections import defaultdict

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


def culc(xx, mod):
    return xx ** 2 % mod


dic = defaultdict(int)
A = x
warps = [A]
indices = [0 for i in range(m + 5)]
count = 1
circle_len = -1
tail_len = -1
while True:
    count += 1
    A = culc(A, m)
    if dic[A] >= 1:
        circle_len = count - indices[A]
        tail_len = count - circle_len - 1
        break
    warps.append(A)
    indices[A] = count
    dic[A] += 1

tail = warps[:tail_len]
circle = warps[tail_len:]

times = (n - tail_len) // circle_len
remainder = (n - tail_len) % circle_len

ans = sum(tail) + times * sum(circle) + sum(circle[:remainder])
print(ans)



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

id = [-1] * M
a = list()
l = 0
total = 0

while(id[X] < 0):
  id[X] = l
  l += 1
  total += X
  a.append(X)
  X = pow(X,2,M)

c = l - id[X]
s = 0
for i in range(id[X],l,1):
  s += a[i]

ans = 0
if N <= c:
  for i in range(N):
    ans += a[i]
else:
  ans += total
  N -= l
  ans += (N//c) * s
  N %= c
  for i in range(N):
    ans += a[id[X] + i]

print(ans)

N, X, M =map(int, input().split())
id = [-1] * M
a = list()
l = 0
total = 0
while(id[X] < 0):
  id[X] = l
  a.append(X)
  total += X
  l += 1
  X = pow(X,2,M)
  
c = l - id[X]
s = 0
for i in range(id[X],l,1):
  s += a[i]
  
ans = 0
if N <= l:
  for i in range(N):
    ans += a[i]
else:
  ans += total
  N -= l
  ans += (N//c) * s
  N %= c
  for i in range(N):
    ans += a[id[X] + i]
print(ans)

n,x,m=map(int,input().split());r,l,k=n,[-1]*m,[]
for i in range(n):
 j=l[x]
 if j>=0:r=i-j;break
 l[x]=i;k+=[x];x=x**2%m;n-=1
print(n//r*sum(k[j:])+sum(k+k[j:n%r+j]))

N, X, M = list(map(int, input().split()))
s = set()
l = list()
ans = 0

A = X
s.add(A)
l.append(A)
ans += A
index = 1
while True:
    Anext = (A * A) % M
    if Anext in s:
        break
    A = Anext
    s.add(A)
    l.append(A)
    ans += A
    index += 1
    if index == N:
        print(ans)
        return

Ai = Anext
index_Ai = l.index(Ai)
len_R = index - index_Ai
len_L = index - len_R
kurikaeshi = sum(l[len_L:])
ans += (N - index) // len_R * kurikaeshi
ans += sum(l[len_L:len_L + (N - index) % len_R])
print(ans)


class DoublingAggregation:
    def __init__(self, nexts, arr, max_n, op, e):
        # op はモノイド
        n = len(nexts)
        self.table = [nexts[:]]
        self.data = [arr[:]]
        self.op = op
        self.e = e
        self.max_n = max_n
        for k in range(max_n.bit_length()-1):
            perm = self.table[-1]
            perm_next = []
            dat = self.data[-1]
            dat_next = []
            for p, d in zip(perm, dat):
                perm_next.append(perm[p])  # perm[p] == perm[perm[idx_perm]]
                dat_next.append(op(d, dat[p]))
            self.table.append(perm_next)
            self.data.append(dat_next)

    def prod(self, idx, n):
        # arr[idx] * arr[nexts[idx]] * arr[nexts[nexts[idx]] * ... を n 回繰り替えした値を返す
        val = self.e
        op = self.op
        for bit, (t, dat) in enumerate(zip(self.table, self.data)):
            if n >> bit & 1:
                val = op(val, dat[idx])
                idx = t[idx]
        return idx, val

    def max_right(self, idx, f):
        # f(arr[idx] * arr[nexts[idx]] * arr[nexts[nexts[idx]] * ... (n 回)) が
        # True である最大の n と、そのときの prod(idx, n)
        n = 0
        val = self.e
        op = self.op
        for bit, t, dat in zip(list(range(len(self.table)-1, -1, -1)), self.table[::-1], self.data[::-1]):
            val_next = op(val, dat[idx])
            if f(val_next):
                val = val_next
                idx = t[idx]
                n |= 1 << bit
        if n > self.max_n:
            n = self.max_n
        return n, idx, val


from operator import add

N, X, M = list(map(int, input().split()))
nexts = [i*i%M for i in range(M)]
arr = list(range(M))
doubling = DoublingAggregation(nexts, arr, N, add, 0)
ans = doubling.prod(X, N)[1]
print(ans)


#繰り返しを探す
N,X,M = list(map(int, input().split()))

#ループ前　ループ中　ループ後　の合計をそれぞれ求め、その和を求める
pre_loop_sum = 0
all_loop_sum = 0
incomplete_loop_sum = 0

loop_flag = False

L = []
L.append(X  % M)

#高速化のため
S = set()

#繰り返しが起きるまでの配列の作成
for i in range(1,N):
    X = pow(X,2,M)

    if X in S:
        loop_flag = True
        break
    else:
        L.append(X)
        S.add(X)

index = L.index(X)

len_L = len(L)

if loop_flag:
    #繰り返しが発生した場合
    #ループ前の合計を取得
    pre_loop_sum = sum(L[0:index])

    #ループ内の合計値、ループの長さ、ループの発生回数の取得
    loop_sum = sum(L[index:len_L])
    loop_len = len_L - index
    loop_count = (N - index) // loop_len

    #ループ中の合計を取得
    all_loop_sum = loop_count * loop_sum

    #ループ仕切れない余り部分の取得
    incomplete_loop_len = (N - index) % loop_len
    incomplete_loop_sum = sum(L[index:index+incomplete_loop_len])
else:
    #繰り返しが発生しない場合
    pre_loop_sum = sum(L)

ans = pre_loop_sum + all_loop_sum + incomplete_loop_sum

print(ans)


n, x, m = map(int, input().split())
a = []
mp = dict()
cnt, tot = 0, 0
while mp.get(x, -1) == -1:
    a.append(x)
    tot += x
    mp[x] = cnt
    cnt += 1
    x = (x * x) % m

if n <= cnt:
    ans = 0
    for i in range(0, n): ans += a[i]
    print(ans)
    return
cycle = 0
rest = cnt - mp.get(x, 0)
for i in range(mp[x], cnt):
    cycle += a[i]
n-= cnt
ans = tot
ans += (n // rest) * cycle
n %= rest
si = mp.get(x, 0)
for i in range(n): ans += a[si + i]
print(int(ans))

n,x,m=map(int,input().split())
id=[-1]*(m+1)
s=[]
c=0
while(id[x]==-1):
    id[x]=c
    c+=1
    s.append(x)
    x=x*x%m
d=c-id[x]
ans=0
if d>=n:
    for i in range(n):
        ans+=s[i]
else:
    for i in range(id[x]):
        ans+=s[i]
    n-=id[x]
    sum=0
    for i in range(d):
        sum+=s[id[x]+i]
    ans+=(n//d)*sum
    n=n%d
    for i in range(n):
        ans+=s[id[x]+i]
print(int(ans))

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))
        return
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)


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

ans=0
sumlist = [X,]
checklist = [-1]*(M+1)
A = X
# checklist[A] = 0

def calcans(start, end, sumlist):
    cnt = end - start + 1
    loop = (N - start - 1) // cnt
    add = N - (cnt * loop) - start
    return (sumlist[end]-sumlist[start-1])*loop + sumlist[start-1+add]

for i in range(1,N):
    A = (A**2) %M
    # print(A)
    if checklist[A-1] != -1:
        # print(f'start: {checklist[A]} end: {i-1}')
        ans = calcans(checklist[A-1], i-1, sumlist)
        # looplen = i-1 - checklist[A] + 1
        # looptimes = (N - checklist[A]-1) // looplen
        # ans += (sumlist[i-1] - sumlist[checklist[A]-1] )* looptimes
        # ans += sumlist[(N-checklist[A]) % looplen + checklist[A]-1]
        # print(f'loop end: {looplen}, {looptimes}')
        break
    elif A == 0:
        ans = sumlist[i-1]
        break
    else:
        checklist[A-1] = i
        sumlist.append(sumlist[-1] + A)
else:
    ans = sumlist[-1]

print(ans)

def main():
    n, x, m = list(map(int, input().split()))
    now = x
    l = [now]
    s = set([now])
    for i in range(n-1):
        now = now*now % m
        if now in s:
            break
        else:
            l.append(now)
            s.add(now)
    if n == len(l):
        print((sum(l)))
        return 0
    i = l.index(now)
    l1 = l[:i]
    l2 = l[i:]
    ans = sum(l1)
    n -= i
    size = len(l2)
    print((ans+((n//size)*sum(l2)+sum(l2[:n % size]))))


main()


N,X,M = map(int, input().split())
id = [-1] * M
l = 0
total = 0
a = list()
while(id[X] == -1):
  a.append(X)
  id[X] = l
  total += X
  l += 1
  X = pow(X,2,M)

c = l - id[X]
s = 0
for i in range(id[X],l,1):
  s += a[i]
ans = 0
if N <= l:
  for i in range(N):
    ans += a[i]
else:
  ans += total
  N -= l
  ans += s * (N//c)
  N %= c
  for i in range(N):
    ans += a[id[X] + i]
print(ans)

n, x, m = map(int, input().split())
 
visit = [0] * m
visit_t = [0] * m
a = [0] *(m+1)
a_sum = [0] *(m+1)
 
a[1] = x
a_sum[1] = x
visit[a[1]] +=1
 
 
flg = True
 
if n == 1:
    print(x)
    return
if x == 0:
    print(0)
    return
 
for i in range(1,n):
    a[i+1] = (a[i]**2)%m
    a_sum[i+1] = a_sum[i] + a[i+1]
    if visit[a[i+1]] == 0:
        visit[a[i+1]] += 1
        visit_t[a[i+1]] = i
    else:
        li = visit_t[a[i+1]] 
        roop = i - li
        roop_sum = a_sum[i]-a_sum[li]
        flg = False
        break
 
if flg:
    print(a_sum[i+1])
    return
 
sum = a_sum[li] 
sum += roop_sum*((n-li)//roop)
sum += a_sum[li + (n-li)%roop] - a_sum[li]
 
print(sum)

def main():
    n, x, m = list(map(int, input().split()))
    a, r = [0]*(m+1), 0
    chk = [False] * (m+1)
    a[0] = x
    for i in range(m):
        tmp = pow(a[i], 2, m)
        if tmp == 0:
            print((sum(a)))
            return
        r = i+1
        if chk[tmp]:
            l = a.index(tmp)
            break
        else:
            chk[tmp] = True
        a[r] = tmp
    print((sum(a[:l]) +
          sum(a[l:r])*((n-l)//(r-l)) +
          sum(a[l:l+(n-l) % (r-l)])))


def __starting_point():
    main()

__starting_point()

n, x, m = map(int, input().split())
mod = [-1] * m
start = 0
last = 0
a = [x]
mod[x] = 0
for i in range(1, m):
  if i >= n:
    break
  a_new = a[-1]**2 % m
  if mod[a_new] == -1:
    mod[a_new] = i
  else:
    start = mod[a_new]
    last = i
    break
  a.append(a_new)

loop_num = 0
remain = 0
if last - start:
  loop_num = (n - start) // (last - start)
  remain = (n - start) % (last - start)
  out = sum(a[:start]) + sum(a[start:last + 1]) * loop_num
  out += sum(a[start:start+remain])
else:
  out = sum(a)

print(out)

import numpy as np

def __starting_point():
  
  n, x, m = list(map(int, input().split()))
  a = [0 for i in range(m + 2)]
  
  #ループを特定するパート
  mod = [0 for i in range(m)]
  loop_start_0 = 0
  loop_start_1 = 0
  loop_exists = 0
  a[0] = x
  for i in range(1, m + 2):
    a[i] = a[i-1]**2 % m
    if mod[a[i]] == 0:
      mod[a[i]] = i
    else:
      loop_start_0 = mod[a[i]]
      loop_start_1 = i
      loop_exists = 1
      break
      
  sum_of_a = 0
  
  if loop_exists:
    #ループが始まる前の和
    for i in range(loop_start_0):
      sum_of_a += a[i]
    
    #ループ部分の和
    loop_sum_of_a = 0
    for i in range(loop_start_0, loop_start_1):
      loop_sum_of_a += a[i]
    
    loop_num = np.floor((n - loop_start_0) / (loop_start_1 - loop_start_0))
    sum_of_a += loop_sum_of_a * loop_num
    
    #最後に余った部分の和
    for i in range(loop_start_0, int(n - (loop_start_1 - loop_start_0) * loop_num)):
      sum_of_a += a[i]
      
  else:
    for i in range(n):
      sum_of_a += a[i]
    
    
  print(int(sum_of_a))
__starting_point()

n,x,m=list(map(int,input().split()))
A=[x]
M=[0]*m
while True:
    x = pow(x,2,m)
    if M[x]==1:
        break
    A.append(x)
    M[x]=1

s=A.index(x)

shuki=len(A)-s

if n<=s:
    print((sum(A[:n])))
else:
    n-=s
    su=sum(A[s:])
    print(((n//shuki)*su+sum(A[s:s+(n%shuki)])+sum(A[:s])))



# -*- coding: utf-8 -*-
import math
n, x, m = list(map(int, input().split()))

appearance = {}
sequence = []
a = x
loopExists = False

# find loop in numerical sequence. loop length < m
# because m << n, for loop should break sooner than n
for _ in range(n):
    appearance[a] = appearance.get(a, 0) + 1
    if appearance[a] == 2:
        loopExists = True
        break
    sequence.append(a)
    a = a * a % m

if not loopExists:
    print((sum(sequence)))
else:
    loopStartIndex = sequence.index(a)
    preLoopNums = sequence[:loopStartIndex]
    loopNums = sequence[loopStartIndex:]
    preLoopLength = len(preLoopNums)
    loopLength = len(loopNums)
    # n = preLoopLength + loopCount * loopLength + rest
    loopCount = (n - preLoopLength) // loopLength
    restLength = (n - preLoopLength) % loopLength
    # total = preLoopTotal + loopTotal * loopCount + restTotal
    preLoopTotal = sum(preLoopNums)
    loopTotal = sum(loopNums)
    restTotal = sum(loopNums[:restLength])
    total = preLoopTotal + loopTotal * loopCount + restTotal
    print(total)


import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
mod = 998244353

n,x,m = rl()
res = [0]*m
nums = []
cnt=0
while True:
    if res[x]==1:
        break
    res[x] = 1
    nums.append(x)
    
    a = x % m
    x = a*a%m
    cnt+=1
#print(res)
circle = nums.index(x)
if n<circle:
    print(sum(nums[:circle]))
else:
    times = (n-circle)//(cnt-circle)
    last = (n-circle)%(cnt-circle)
    #print(times)
    #print(last)
    #print(circle)
    print(sum(nums[:circle]) + sum(nums[circle:])*times + sum(nums[circle:circle+last]))

#高々Mの繰り返し
N,X,M =list(map(int,input().split()))
memo = [0]*(2*M+1)
val_idx = {X:1}
idx_val = {1:X} 
seen = set([X])
memo[1]=X

loop_length = 0
for i in range(2,N+1):
    X = pow(X,2,M)
    if X not in seen:#まだloopしてない
        seen.add(X)
        val_idx[X]=i
        idx_val[i]=X
        memo[i]+=memo[i-1]+X
    else:#loopに達した
        loop_start_val = X
        loop_start_idx = val_idx[X]
        loop_length = i-loop_start_idx
        break
if loop_length == 0:
    print((memo[N]))
else:
    rest_num = (N-loop_start_idx+1)%loop_length
    loop_num =(N-loop_start_idx+1)//loop_length
    ans = (memo[loop_start_idx+loop_length-1]-memo[loop_start_idx-1])*loop_num+memo[loop_start_idx-1+rest_num]
    print(ans)


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

checked_val = [0] * M
sum_list = [X]
a = X

def calc_ans(sum_list, start_idx, end_idx):
    loop_len = end_idx - start_idx + 1
    loop_times = (N - start_idx - 1) // loop_len
    add = N - (loop_len * loop_times) - start_idx
    return ((sum_list[end_idx] - sum_list[start_idx - 1]) * loop_times + sum_list[start_idx - 1 + add])

for i in range(1, N):
    a = (a ** 2) % M
    if checked_val[a - 1] != 0:
        ans = calc_ans(sum_list, checked_val[a - 1], i - 1)
        break
    elif a == 0:
        ans = sum_list[i - 1]
        break
    else:
        checked_val[a - 1] = i
        sum_list.append(sum_list[-1] + a)
else:
    ans = sum_list[-1]
print(ans)

n,x,m=map(int,input().split())
an=[0]*(m)
check=[0]*m
an[0]=x
check[x]=1
for i in range(1,m+1):
  x=(x**2)%m
  if check[x]!=0:
    break
  else:
    check[x]=i+1
    an[i]=x

num=i-check[x]+1
ans=sum(an[:(check[x]-1)])
kazu=n-len(an[:(check[x]-1)])
re=sum(an[check[x]-1:i])
ans+=(kazu//num)*(re)
ans+=sum(an[check[x]-1:i-(num-(kazu%num))])
print(ans)

def main():
    n, x, m = list(map(int, input().split()))
    s = set()
    L = []
    ans = 0
    while n > 0:
        s.add(x)
        L.append(x)
        ans += x
        x = x * x % m
        n -= 1
        if x in s:
            break       
    else:
        print(ans)
        return
    L = L[L.index(x):] 
    q, r = divmod(n, len(L))
    ans += sum(L) * q
    ans += sum(L[:r])
    print(ans)
    
def __starting_point():
    main()

__starting_point()

n, x, m = list(map(int, input().split()))
ls = [-1] * (m+1) 
a = []
tot = 0
cnt = 0
while ls[x] == -1:
    a.append(x)
    tot += x
    ls[x] = cnt
    cnt += 1
    x = (x*x) % m 

if n <= cnt :
    ans = 0
    for i in range(n):
        ans += a[i]
    print(ans)
    return
cycle = 0
rest = cnt - ls[x]
for i in range(ls[x], cnt):
    cycle += a[i]
n -= cnt 
ans = tot
ans += (n//rest) * cycle 
n %= rest
si = ls[x]
for i in range(n):
    ans += a[si + i]
print(ans)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
#mod = 10 ** 9 + 7 
mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X, M = MAP()

check = [0]*(10**5+1)
sum_acc = [0]

i = X
cnt = 0
while check[i] < 2 and cnt < N:
	check[i] += 1
	cnt += 1
	sum_acc.append(sum_acc[-1]+i)
	i = i**2%M

if cnt == N:
	print(sum_acc[-1])
	return

cnt_1 = check.count(1)
cnt_2 = check.count(2)
loop_sum = (sum_acc[-1] - sum_acc[cnt_1])//2


ans = sum_acc[cnt_1]
ans += loop_sum*((N-cnt_1)//cnt_2)
ans += sum_acc[cnt_1+((N-cnt_1)%cnt_2)] - sum_acc[cnt_1]

print(ans)

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

ans = x
x0 = x
memo0 = [0] * (m + 1)
memo1 = [0] * (m + 1)
pair = [0, 0]

for i in range(1, n):
    x1 = (x0%m * x0%m) % m
    if memo0[x1] != 0:
        pair = [memo0[x1], i-1]
        break
    else:
        memo0[x1] = i
        memo1[i] = memo1[i-1] + x1
        x0 = x1
        pair = [0, i]

if pair[1] == n - 1:ans = memo1[pair[1]] + x
else:
    i, j = pair[0], pair[1]
    s0i = memo1[i-1] + x
    sij = memo1[j] - memo1[i-1]
    t0 = (n - i) // (j - i + 1)
    t1 = (n - i) % (j - i + 1)
    sje = memo1[t1 + i - 1] - memo1[i-1]
    ans = s0i + sij * t0 + sje

print(ans)

n,x,m = list(map(int, input().split()))
firstOcc = [-1]*(m+2)
arr = []
a = x
for i in range(m+2):
    if firstOcc[a] != -1:
        break
    arr.append(a)
    firstOcc[a] = i
    a = a*a%m

ans = sum(arr[:min(n,firstOcc[a])])
cycleLen = len(arr) - firstOcc[a]
cycleSum = sum(arr[firstOcc[a]:])
ans += cycleSum * ((n-firstOcc[a]) // cycleLen)
leafLen = ((n-firstOcc[a]) % cycleLen)
ans += sum(arr[firstOcc[a] : firstOcc[a]+leafLen])
print(ans)
#print(firstOcc[a], cycleLen, leafLen, len(arr))
#print(arr)


import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,X,M=i_map()

	Y = X

	went_array = []
	for i in range(0,M):
		went_array.append(-1)

	loop_flag = False
	first = -1
	second = -1
	value = -1
	for i in range(0,N):

		if(went_array[Y] != -1):
			loop_flag = True
			first = went_array[Y]
			second = i
			value = Y
			break

		went_array[Y] = i
		Y = (Y*Y) % M

	if(loop_flag == False):
		Z = X
		sum = 0

		for i in range(0,N):
			sum += Z
			Z = (Z*Z)%M

		print(sum)

	else:
		Z = X
		sum1 = 0
		for i in range(0,first):
			sum1 += Z
			Z = (Z*Z)%M

		Z = value
		cum = []
		cum.append(Z)
		Z = (Z*Z) %M
		for i in range(1,second-first):
			cum.append(cum[i-1]+Z)
			Z = (Z*Z) %M

		sum2 = ((N-first)//(second-first))*cum[second-first-1]

		if((N-first)%(second-first) == 0):
			print(sum1 + sum2)
		else:
			sum3 = cum[((N-first)%(second-first)-1)]
			print(sum1 + sum2 + sum3)


	return

def __starting_point():
	main()
__starting_point()

# 参考
# https://atcoder.jp/contests/abc179/submissions/16890682

n, x, m = map(int, input().split())
check = [False] * (10**5 + 10)
check_list = [x]
a = x
# ループを見つける
for i in range(n):
    a = (a * a) % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)
 
# ループの長さを算出
index = check_list.index(a)
# ループはいる前のやつ
loop_bef = check_list[0:index]
# ループのやつ
loop = check_list[index:]
 
# ループが何周あるのかと，ループ終わりがいくつ要素あるかを計算
loop_num = (n - len(loop_bef)) // len(loop)
after_loop = (n - len(loop_bef)) % len(loop)
 
# ループ前+ループのsum*ループ数+ループ後のsumが答え
ans = sum(loop_bef) + sum(loop) * loop_num + sum(loop[:after_loop])
 
print(ans)

import sys

input = sys.stdin.readline

N, X, M = map(int, input().split())
LIST = [X]
SET = {X}

a = X

while True:
    if a * a % M in SET:
        break
    else:
        a = a * a % M
        LIST.append(a)
        SET.add(a)

# 繰り返しがaから始まる
# SETには順番が記録されていないのでLISTを使う
start = LIST.index(a * a % M)
LEN = len(LIST)

if N <= LEN:
    print(sum(LIST[:N]))
else:
    LoopTimes, Excess = divmod(N-LEN, LEN-start)
    LoopSum = sum(LIST[start:]) * LoopTimes
    ExSum = sum(LIST[start:start+Excess])
    print(sum(LIST[:]) + LoopSum + ExSum)

N, X, M = map(int, input().split())
A = X
loop = {A: 1}
sums = [0, A]
start = 0
end = 0
for i in range(2, M+2):
    A = (A ** 2) % M
    if A in loop:
        start = loop[A]
        end = i
        sums.append(sums[-1] + A)
        break
    sums.append(sums[-1] + A)
    loop[A] = i
answer = sums[start]
N -= start
answer += (N // (end - start)) * (sums[end] - sums[start])
answer += sums[start + N % (end - start)] - sums[start]
print(answer)

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

A = [X]
B = [0, X]
S = set(A)

while not A[-1] * A[-1] % M in S:
    V = A[-1] * A[-1] % M
    B.append(B[-1] + V)
    A.append(V)
    S.add(V)

idx = A.index(A[-1] * A[-1] % M)

ans = 0

if idx < N:
    l = len(A) - idx
    ans += B[idx]
    N -= idx

    ans += (B[-1] - B[idx]) * (N // l)
    ans += B[idx + N % l] - B[idx]

    print(ans)
else:
    print(B[N])

# import itertools
# import math
# from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, X, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

#def make_divisors(n):
#    lower_divisors , upper_divisors = [], []
#    i = 1
#    while i*i <= n:
#        if n % i == 0:
#            lower_divisors.append(i)
#            if i != n // i:
#                upper_divisors.append(n//i)
#        i += 1
#    return lower_divisors + upper_divisors[::-1]

# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

# if gcd_list(A) > 1:
#     print("not coprime")
#     return

# 高速素因数分解準備
#MAXN = 10**6+10
#sieve = [i for i in range(MAXN+1)]
#p = 2
#while p*p <= MAXN:
#    if sieve[p] == p:
#        for q in range(2*p, MAXN+1, p):
#            if sieve[q] == q:
#                sieve[q] = p
#    p += 1

A = [X]
st = set(A)
last_num = 0
for i in range(1, N):
    a_i = A[-1] ** 2 % M
    if a_i in st:
        last_num = a_i
        break
    A.append(a_i)
    st.add(a_i)
else:
    print(sum(A))
    return

#print("loop case ha mada dekitenai")

loop_start = A.index(last_num)

A_before_loop = A[:loop_start]
A_loop_part = A[loop_start:]

q, mod = divmod((N - len(A_before_loop)), len(A_loop_part))

print(sum(A_before_loop) + sum(A_loop_part) * q + sum(A_loop_part[:mod]))

n, x, m = list(map(int, input().split()))
visited = [None] * m
visited[x] = 1
a = x
s = [0] * min(n + 1, m + 1)
s[1] = x
for i in range(2, n + 1):
    a = a**2 % m
    if visited[a]:
        d = s[i - 1] - s[visited[a] - 1]
        k = i - visited[a]
        r = (n - visited[a]) % k + visited[a]
        l = (n - visited[a]) // k
        print((s[r] + l * d))
        return
    visited[a] = i
    s[i] = s[i - 1] + a
print((s[n]))


from collections import deque

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

A = deque()
G = [-1 for i in range(m)]
t = 0
total = 0
while G[x] == -1:
    A.append(x)
    G[x] = t
    t += 1
    total += x
    x = (x*x) % m

cycle = t - G[x]
s = 0
for i in range(cycle):
    s += A[G[x] + i]

ans = 0
if n < t:
    for i in range(n): ans += A[i]
else:
    n -= t
    ans = total + s * (n // cycle)
    for i in range(n % cycle): ans += A[G[x] + i]
print(ans)

def printAns(first, start, end, s):
    cnt = end - start + 1
    loop = (N - start - 1) // cnt
    add = N - (cnt * loop) - start
    print((s[end]-s[start-1])*loop + s[start-1+add])
    
    
N, X, M = map(int, input().split())

check = [0] * M
m = [X]
a = X

for i in range(1, N):
    a = (a**2)%M
    if check[a-1] != 0:
        printAns(0, check[a-1], i-1, m)
        return
    elif a == 0:
        print(m[i-1])
        return
    check[a-1] = i
    m.append(m[-1] + a)
else:
    print(m[-1])

#高々Mの繰り返し
N,X,M =list(map(int,input().split()))
memo = [0]*(2*M+1)#最長2Mまでloopするはず
val_idx = {X:1}
seen = set([X])
memo[1]=X

loop_length = 0
for i in range(2,N+1):
    X = pow(X,2,M)
    if X not in seen:#まだloopしてない
        seen.add(X)
        val_idx[X]=i
        memo[i]+=memo[i-1]+X
    else:#loopに達した
        loop_start_val = X
        loop_start_idx = val_idx[X]
        loop_length = i-loop_start_idx
        break
if loop_length == 0:
    print((memo[N]))
else:
    rest_num = (N-loop_start_idx+1)%loop_length
    loop_num =(N-loop_start_idx+1)//loop_length
    ans = (memo[loop_start_idx+loop_length-1]-memo[loop_start_idx-1])*loop_num+memo[loop_start_idx-1+rest_num]
    print(ans)


import numpy as np


def main():
    n, x, m = list(map(int, input().split()))
    a, r, ans = np.zeros((m+1), np.int64), 0, 0
    a[0] = x
    for i in range(m):
        tmp = np.power(a[i], 2) % m
        if tmp == 0:
            print((sum(a)))
            return
        r = i+1
        if tmp in a:
            l = np.where(a == tmp)[0][0]
            ans = sum(a[l:r])*((n-l)//(r-l))
            ans += sum(a[l:l+(n-l) % (r-l)])
            break
        a[r] = tmp
    print((ans+sum(a[:l])))


def __starting_point():
    main()

__starting_point()

def main():
    n, x, m = list(map(int, input().split()))
    a, r, ans = [x], 0, 0
    chk = [False] * (m+1)
    for i in range(m):
        tmp = pow(a[i], 2, m)
        if tmp == 0:
            print((sum(a)))
            return
        r = i+1
        if chk[tmp]:
            l = a.index(tmp)
            ans = sum(a[l:r])*((n-l)//(r-l))
            ans += sum(a[l:l+(n-l) % (r-l)])
            break
        else:
            chk[tmp] = True
        a.append(tmp)
    print((ans+sum(a[:l])))


def __starting_point():
    main()

__starting_point()

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

A = X
loop_dict = {A: 1}
ct = 1
while True:
    ct += 1
    A = A ** 2 % M
    if A in loop_dict:
        break
    else:
        loop_dict[A] = ct
        if ct == N:
            # 一周しなかった場合
            print((sum(loop_dict)))
            return

loop_length = len(loop_dict) - loop_dict[A] + 1
tail_length = loop_dict[A] - 1
loop = [0] * loop_length
tail = [0] * tail_length

for x, i in list(loop_dict.items()):
    if i <= tail_length:
        tail[i - 1] = x
    else:
        loop[i - tail_length - 1] = x

d, m = divmod(N - tail_length, loop_length)
print((sum(tail) + sum(loop) * d + sum(loop[:m])))


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

def A(x, m):
    return (x**2)%m

now = x
ans = 0
streak = []
used = set()
loop = False
while n > 0:
    if now in used:
        loop = True
        break
    used.add(now)
    ans += now
    streak.append(now)
    now = A(now, m)
    n-=1

if loop:
    loop_sum = 0
    loop_streak = []
    for j, item in enumerate(streak[::-1]):
        loop_sum += item
        loop_streak.append(item)
        if item == now:
            loop_length = j+1
            break
    ans += (n//loop_length)*loop_sum
    loop_streak.reverse()
    ans += sum(loop_streak[:n%loop_length])

print(ans)

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

t,i,c,d=0,0,[0]*-~m,[0]*-~m
while i<n:
  i,t=i+1,t+x
  c[x],d[i]=i,t
  x=x**2%m
  if c[x]:
    break

if i!=n and x!=0:
  p=c[x]-1
  t=(d[i]-d[p])*((n-p)//(i-p))+d[p+(n-p)%(i-p)]

print(t)


n,x,m=map(int,input().split());l,k,i,j=[-1]*m,[],0,-1
while j<0:l[x]=i;k+=[x];x=x**2%m;n-=1;j=l[x];i+=1
r=i-j;print(n//r*sum(k[j:])+sum(k+k[j:n%r+j]))

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

rem = [-1]*(m+1)
rem[x] = 1
now = x
s = []

while True:
    s.append(now)
    next = (now*now) % m
    if rem[next] == -1:
        rem[next] = rem[now] + 1
    else:
        cycle_start = next
        break

    now = next


ans = 0
for i in range(rem[cycle_start]-1):
    if n >= 1:
        n -= 1
        ans += s[i]
    else:
        break

cycle_sum = sum(s[rem[cycle_start]-1:])
cycle_length = max(rem) - rem[cycle_start] + 1

ans += cycle_sum * (n // cycle_length)
n -= cycle_length * (n//cycle_length)

now = rem[cycle_start] - 1
while n > 0:
    ans += s[now]
    n -= 1
    now += 1

print(ans)


n, x, m = list(map(int, input().split()))
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m
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))