Problem:
 Score : 500 points    Problem Statement 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 1 6 2 1001      Sample Output 1 1369  The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369 .       Sample Input 2 1000 2 16      Sample Output 2 6  The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6 .       Sample Input 3 10000000000 10 99959      Sample Output 3 492443256176507

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)









INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def next_val(An, M):
    return (An * An) % M

def run():
    N, X, M = mapline()
    arr = [X]
    valset = {}
    valset[X] = 0
    while True:
        an = arr[-1]
        next_a = next_val(an, M)
        if not next_a in valset.keys():
            arr.append(next_a)
            valset[next_a] = len(arr) - 1
        else:
            break
    idx1 = valset[next_a]
    K = len(arr)
    ans = 0
    if N > idx1:
        ans += sum(arr[:idx1])
    else:
        ans += sum(arr[:N])
        print(ans)
        return

    N -= idx1
    l = K - idx1
    sums = sum(arr[idx1:])
    cycle = N // l
    ans += sums * cycle
    N %= l
    ans += sum(arr[idx1:idx1+N])
    print(ans)






if __name__ == "__main__":
    run()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

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

    mod=M

    dp=[[0,0] for _ in range(M)]
    
    cnt=1
    tot=X
    dp[X]=[cnt,tot]
    while cnt<N:
        X=X*X%M
        printe(X)
        if X==0:
            print(tot)
            return
        if not dp[X][0]:
            cnt+=1
            tot+=X
            dp[X]=[cnt,tot]
            if cnt==N:
                print(tot)
                return
        else:
            break
    syuki=cnt+1-dp[X][0]
    val=X+tot-dp[X][1]
    d,a=divmod(N-dp[X][0],syuki)
    tot=dp[X][1]
    tot+=val*d
    for i in range(a):
        X=X*X%M
        tot+=X
    print(tot)


if __name__ == "__main__":
    main()

Solution (Python):
n,x,m=map(int,input().split())
a=[x]
check=set()
check.add(x)

past=x
cnt=1
while(1):
  now=(past**2)%m
  if now not in check:
    a.append(now)
    check.add(now)
    cnt+=1
    past=now
    if cnt==n:
      print(sum(a))
      exit()
  else:
    
    time=len(a)-a.index(now)
    
    pre=a.index(now)
    
    pre_sum=sum(a[:a.index(now)])
    
    time_sum=((n-pre)//time)*sum(a[a.index(now):len(a)])+sum(a[a.index(now):a.index(now)+(n-pre)%time])
    
    print(pre_sum+time_sum)
    exit()

Solution (Python):
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]


MOD = 998244353
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic


def solve(N, X, M):
    seen = {X: 0}
    t = 0
    while True:
        t += 1
        if t == N:
            return sum(seen)
        X2 = X*X%M
        if X2 not in seen:
            seen[X2] = t
            X = X2
            continue
        break

    base = sum(seen)
    N -= t
    u = seen[X2]
    mu = t - u
    period = sum(k for k,v in seen.items() if v >= u)
    Q, R = divmod(N, mu)
    
    
    base += Q * period

    X = X2
    while R:
        base += X
        X *= X
        X %= M
        R -= 1

    return base

def brute(N, X, M):
    A = [X]
    while len(A) < N:
        A.append(A[-1] ** 2 % M)
    
    
    return sum(A)





if 0:
    for n in xrange(1, 100):
        for x in xrange(1, 10):
            for m in xrange(x + 1, 100):
                if solve(n,x,m) != brute(n,x,m):
                    print("!", n,x,m, ';',solve(n,x,m), brute(n,x,m))
                    break
            
print solve(*rrm())

Solution (Python):
N, X, M = map(int, input().split())
ans = X
loop = 1
def f(a):
    return (a * a) % M


appear = [0] * (M + 1)
tmp = f(X)
appear[X] = loop
while appear[tmp] == 0:
    loop += 1
    appear[tmp] = loop
    tmp = f(tmp)

loopstart = tmp
tmp = X
before_loop_sum = 0
before_loop_len = 0
while tmp != loopstart:
    before_loop_sum += tmp
    before_loop_len += 1
    tmp = f(tmp)

loop_sum = loopstart
loop_len = 1
tmp = f(loopstart)
while tmp != loopstart:
    loop_sum += tmp
    loop_len += 1
    tmp = f(tmp)

if N < before_loop_len:
    tmp = X
    ans = 0
    for i in range(N):
        ans += tmp
        tmp = f(tmp)
else:
    N -= before_loop_len
    ans += before_loop_sum
    n_loop = N // loop_len
    N -= loop_len * n_loop
    ans += n_loop * loop_sum
    tmp = loopstart
    for i in range(N):
        ans += tmp
        tmp = f(tmp)
print(ans- X)

Solution (Python):
def main():
    n, x, mod = map(int, input().split())
    a = x
    val = set()
    val_arr = []
    idx = {}
    rep = []
    init = []
    for i in range(n):
        if a in val:
           rep = val_arr[idx[a]:]
           init = val_arr[:idx[a]]
           break
        else:
            idx[a] = i
            val.add(a)
            val_arr.append(a)
            a = a ** 2 % mod
    if len(rep) > 0:
        ans = sum(init)
        ans += sum(rep) * ((n - len(init)) // len(rep))
        ans += sum(rep[:(n - len(init)) % len(rep)])
    else:
        ans = sum(val_arr)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,x,m=map(int,input().split())
seen=[-1]*(2*10**5)
A=[0]*(2*10**5)
A[0]=x


now=x ;seen[x]=0
for i in range(1,n):
    now= (now**2)%m 
    A[i]=now
    if seen[now]!=-1:
        st = sum(A[:seen[now]])
        gr = sum(A[seen[now]: i ])
        naga= i-seen[now]
        ret = (n-seen[now])//naga
        print(st+ gr*ret + sum(A[seen[now]: seen[now]+(n-seen[now])%naga]))
        exit()
    else:
        seen[now]=i
else:
    print(sum(A[:n]))

Solution (Python):
N,X,M = map(int,input().split())
A = [0]*M
S = 0
r = X % M
A[r] = 1
d = 0
I = 0
for i in range(1,M+1):
    r = (r*r) % M
    if A[r] == 0:
        A[r] = i+1
    else:
        I = A[r]
        j = i+1
        d = j-I
        break
r = X
for i in range(I):
    S += r
    r = (r*r) % M
if d != 0:
    t,u = (N-I)//d,(N-I)%d
    s = 0
    for i in range(d):
        s += r
        r = (r*r) % M
    S += s*t
    for i in range(u):
        S += r
        r = (r*r) % M
print(S)

Solution (Python):
n, x, m = map(int, input().split())
nxt = [-1] * m
now = x
while nxt[now] == -1:
    nxt[now] = now * now % m
    now = nxt[now]
junction = now
ans = x
now = x
n = n - 1
while n and now != junction:
    now = nxt[now]
    n -= 1
    ans += now
if n == 0:
    print(ans)
    exit()

llen = 1
lsum = junction
now = nxt[junction]
while now != junction:
    llen += 1
    lsum += now
    now = nxt[now]
ans += lsum * (n // llen)
n = n % llen

now = junction
while n:
    now = nxt[now]
    n -= 1
    ans += now
print(ans)

Solution (Python):
def main():
    N, X, M = map(int, input().split())
    a = X
    r = a
    i = 1
    S = {X: (0, 0)}
    ns = True
    while i < N:
        an = (a * a) % M
        if an == 0:
            break
        if ns and an in S:
            l = S[a][1] - S[an][1] + 1
            skip = (N - i - 1) // l
            r += (r - S[an][0]) * skip
            i += l * skip
            ns = False
        if i >= N:
            break
        a = an
        S[a] = (r, i)
        r += a
        i += 1

    return r


print(main())

Solution (Python):
N,X,M = 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)

Solution (Python):
N, X, M = map(int, input().split())
Memo = [-1] * M
Cumsum = [0] * M
cumsum = X
x = X

for i in range(N):
    if Memo[x] != -1:
        break
    Memo[x] = i
    Cumsum[x] = cumsum
    x = x * x % M
    cumsum += x
else:
    print(cumsum-x)
    exit()
loop_length = i - Memo[x]
init_sum = Cumsum[x]
loop_sum = cumsum - init_sum

n_from_init = N - i - 1
n_loops, n_from_loopend = divmod(n_from_init, loop_length)
cumsum += n_loops * loop_sum

for i in range(n_from_loopend):
    x = x * x % M
    cumsum += x

print(cumsum)

Solution (Python):
def main():
    n,x,m = map(int,input().split())
    if n == 1:
        print(x)
        return
    
    start = x
    arr = [x]
    visited = set()
    visited.add(x)
    prev = x
    curr = pow(prev,2,m)
    while curr not in visited:
        visited.add(curr)
        arr.append(curr)
        prev = curr
        curr = pow(prev,2,m)

    total = 0
    index = 0
    while n > 0 and index < len(arr):
        total += arr[index]
        n -= 1
        index += 1

    while arr[0] != curr:
        arr.pop(0)

    total += sum(arr)*(n//len(arr))
    for i in range(n%len(arr)):
        total += arr[i]

    print(total)

main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    n,x,m=MI()
    seq=[x]
    y=x
    for i in range(2*10**5+10):
        y=((y%m)**2)%m
        seq.append(y)
        
    
    z=seq[m-1]
    repeat=[]
    for i in range(1,m+1):
        repeat.append(seq[i+m-1])
        if seq[i+m-1]==z:
            rep=i
            
            break
    
    if n<=m:
        print(sum(seq[:n]))
    else:
        ans=sum(seq[:m])
        
        counts=(n-m)//rep
        S=sum(repeat)
        ans+=S*counts
        rest=(n-m)%rep
        last=m-1+counts*rep
        '''for i in range(last+1,n):
            ans+=repeat[(i-(m-1))%rep]'''
        for i in range(rest):
            ans+=repeat[i]
        print(ans)
    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Solution (Python):


def solve(N,X,M):
    if X == 0:
        return 0
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


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

Solution (Python):
n,x,m=map(int,input().split())
p=[0]*(m+1)
a=x
t=0
s=0
for i in range(2*m):
    if p[a]==1:
        p[a]=2
        break
    else:
        p[a]=1
        a=a**2%m
a=x
S=0
for i in range(2*m):
    if p[a]==1:
        s+=1
        S+=a
        a=a**2%m
    else:
        s+=1
        S+=a
        break
T=0
A=0
for i in range(2*m):
    a=a**2%m
    t+=1
    T+=a
    if p[a]==2:
        A=a
        break


a=x
if n<=s:
    ans=0
    for i in range(n):
        ans+=a
        a=a**2%m
    print(ans)
else:
    ans=S
    a=A
    n-=s
    ans+=(n//t)*T
    n=n%t
    for i in range(n):
        a=a**2%m
        ans+=a
    print(ans)

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

ans = 0
A = []
T = [-1]*M
i = 0
f = False
while i<N:
  if T[X]!=-1 and not f:
    f = True
    ans += sum(A[T[X]:])*((N-i)//(i-T[X]))
    i += (N-i)//(i-T[X])*(i-T[X])
    continue
  A += [X]
  T[X] = i
  ans += X
  X = X*X%M
  i += 1
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

n,x,m=map(int,input().split())
values=[]
s=set()
loop_start=-1
for i in range(n):
    if x in s:
        loop_start=values.index(x)
        break
    values.append(x)
    s.add(x)
    x=(x*x)%m
if loop_start==-1:
    ans=sum(values)
    print(ans)
    exit()
else:
    ans=sum(values[:loop_start])
    loops=values[loop_start:]
    loops_sum=sum(loops)
    n-=loop_start
    l=len(loops)
    ans+=n//l*loops_sum+sum(loops[:n%l])
    print(ans)

Solution (Python):


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

R = [-1] * M
R[X % M] = 0
A = [0] + [X % M]
a = X
for i in range(1, N):
  a **= 2
  a %= M
  if R[a] == -1:
    R[a] = i
    A += [A[-1] + a]
  else:
    print(X - X % M + (A[-1] - A[R[a]]) * ((N - R[a]) // (i - R[a])) + A[R[a] + (N - R[a]) % (i - R[a])])
    exit()
print(A[-1] + X - X % M)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

xs = [0] * M
cur = X
cicle = 0
A = []
for i in range(M + 5):
    v = cur % M 
    if xs[v] != 0:
        A.append(v)
        cicle = i
        break
    xs[v] += 1
    A.append(v)
    cur *= cur
    cur %= M

start = 0
for i in range(cicle):
    if A[i] == A[-1]:
        start = i


l = cicle - start
ans = sum(A[0:start])
ans += ((N - start) // l) * sum(A[start:-1])
ans += sum(A[start:start+((N - start) % l)])

print(ans)

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

table = [0]*m

def calc(init,iter):
    ret = 0
    for _ in range(iter):
        ret += init
        init = (init*init)%m
    return ret

ret = x
cur = x % m
table[cur] = 1
for rnd in range(2,min(m+2,n+1)):
    cur = (cur*cur) % m
    if table[cur]:
        per = rnd - table[cur]
        persum = calc(cur,per)
        rnds = (n - rnd) // per
        ret += rnds*persum
        ret += calc(cur,n - rnd - per*rnds+1) 
        
        break
    else:
        table[cur] = rnd
        ret += cur



print(ret)

Solution (Python):
n,x,m=[int(i) for i in raw_input().split()]
x%=m
a=[x]
d={}
d[x]=0
pos=-1
for i in range(1,min(n,100000)):
    t=(a[-1])**2
    t%=m
    if(d.get(t,-1)!=-1):
        pos=d[t]
        break
    d[t]=i
    a.append(t)
s=0
for i in a:
    s+=i
if pos!=-1:
    n-=len(a)
    a=a[pos:]
    s1=0
    for i in a:
        s1+=i
    s+=s1*(n/len(a))
    n%=len(a)
    for i in range(n):
        s+=a[i]
print s

Solution (Python):
N,X,M = map(int,input().split())
cur = X
S = set([X])
while True:
    nA = cur**2 % M
    if nA in S:
        break
    S.add(nA)
    cur = nA
loop = [nA]
while True:
    ne = loop[-1]**2 % M
    if ne == nA:
        break
    loop.append(ne)
ll = len(loop)
sl = sum(loop)
ans = [X]
while True:
    ne = ans[-1]**2 % M
    if ne == nA:
        break
    ans.append(ne)
la = len(ans)
if N <= la:
    print(sum(ans[:N]))
else:
    loop_num = (N-la)//ll
    loop_head = (N-la) % ll
    print(sum(ans)+sl*loop_num+sum(loop[:loop_head]))

Solution (Python):
from itertools import accumulate

N, X, M = map(int, input().split())
s = []
A = X
ind = {}
i = 0
while A not in ind:
    s.append(A)
    ind[A] = i
    A = A * A % M
    i += 1
L = i - ind[A]
s = [0] + list(accumulate(s))
ans = s[ind[A]] + (s[-1] - s[ind[A]]) * ((N - ind[A]) // L) + s[ind[A] + (N - ind[A]) % L] - s[ind[A]]
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
li = [x]
se = {x}
for i in range(n-1):
    x = x*x%m
    if x==0:
        print(sum(li))
        exit(0)
    if x in se:
        idx = li.index(x)
        break
    li.append(x)
    se.add(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)

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

LOOP = [X]
wk = X
s = set()
s.add(X)
flg = True
for i in range(N-1):
  a = wk * wk % M
  if a == 0:
    print(sum(LOOP))
    exit(0)
  if a in s:
    wk = a
    flg = False
    break
  LOOP.append(a)
  s.add(a)
  wk = a

if flg:
  print(sum(LOOP))
else:
  for i in range(len(LOOP)):
    if LOOP[i] == wk:
      beg_i = i
      break
  fin_i = len(LOOP) -1
  ans = sum(LOOP[:beg_i])
  N -= beg_i
  L = LOOP[beg_i:]
  LS = len(L)
  
  ans += sum(L) * (N//LS)
  N = N % LS
  ans += sum(L[:N])
  print(ans)

Solution (Python):
def main():
    n, x, m = map(int, input().split())
    dic = {}
    p = 0
    while not x in dic:
        p += 1
        dic[x] = p
        x = (x**2) % m
    if n <= p:
        ans = 0
        for ky in dic.keys():
            if dic[ky] <= n:
                ans += ky
        print(ans)
    else:
        ans = 0
        for ky in dic.keys():
            ans += ky
        n -= p
        q = dic[x]
        ln = p - q + 1
        tmp = 0
        for ky in dic.keys():
            if q <= dic[ky] <= p:
                tmp += ky
        tmp *= n // ln
        ans += tmp
        n %= ln
        for ky in dic.keys():
            if q <= dic[ky] < q + n:
                ans += ky
        print(ans)

if __name__ == "__main__":
    main()

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, x, m = na()
    ans = x
    l = [x]
    a = x
    for i in range(n-1):
        a = a**2
        a %= m
        if a == 0:
            ans += a
            print(ans)
            quit()
        if a in l:
            
            j = l.index(a)
            r = i - j + 1
            res = sum(l[j:])
            k = ((n-i-1)%r)
            
            ans += (n-i-1)//r * res + sum(l[j:(j+k)])
            break
        l.append(a)
        ans += a
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n,x,m=map(int,input().split())
ary=[x]
ans=x
d={x:0}
i=1
while x and i<n and (x**2)%m not in d:
  x=(x**2)%m
  ans+=x
  d[x]=i
  ary.append(x)
  i+=1
if x==0 or i==n:
  print(ans)
  exit()
s=d[(x**2)%m]
l=i-s
suml=sum(ary[s:])
tmp=n-i
ans+=suml*(tmp//l)
ans+=sum(ary[s:s+tmp%l])
print(ans)

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

exist = [False] * M 
exist[X] = True

A = [X]

while True:
    nex = A[-1]*A[-1] % M
    A.append(nex)
    if exist[nex]:
        break
    else:
        exist[nex] = True

L = len(A)
idx = 0
for i in range(L):
    if A[i] == A[-1]:
        idx = i
        break

ans = 0
for i in range(idx):
    ans += A[i]
    N -= 1
    if(N < 0): exit()

B = A[idx:(L-1)]

ans += (sum(B)*(N//len(B)) + sum(B[:(N%len(B))]))
print(ans)

Solution (Python):
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1



import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    
    n, x, m = map(int, input().split())
    if n == 1:
        print(x)
        quit()
    
    
    
    
    ans = x
    st = set()
    from collections import deque
    a = deque([])
    xc = x
    n -= 1
    i = -1
    for i in range(n):
        xc = (xc * xc) % m
        if xc in st:break
        a += [xc]
        st.add(xc)
    if i != n-1:
        while a[0] != xc and n:
            ans += a.popleft()
            n -= 1
    total = sum(a)
    ans += (total * ((n)//(len(a))))
    for i in range((n) % len(a)):
        ans = (ans + a[i])
    print(ans)

Solution (Python):
n, x, m = [int(i) for i in input().split(" ")]

vis = [-1] * m
sq = [(i*i)%m for i in range(m)]

cur = x
y = x
flag = False
for i in range(n):
  if vis[cur] >= 0:
    flag = True
    break
  vis[cur] = i
  cur = (cur*cur)%m

cycle = max(vis) - vis[cur] + 1

ans = 0
if not flag:
  for i in range(n):
    ans += y
    y = (y*y)%m
    
  print(ans)
elif n <= vis[cur]:
  for i in range(min(n, vis[cur])):
    ans += x
    x = (x*x)%m
  
  print(ans)
else:
  for i in range(min(n, vis[cur])):
    ans += x
    x = (x*x)%m
  y = x
  rem = n - vis[cur]
  cyclesum = 0
  for i in range(cycle):
    cyclesum += y
    y = (y*y)%m
  total = rem//cycle
  extra = rem - cycle*total
  ans += cyclesum*total
  
  for i in range(extra):
    ans += y
    y = (y*y)%m
  print(ans)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n,x,m = MAP()

temp = [x]

present = [-1]*(m+1)

present[x] = 0

i,j = -1, -1

for iter in range(1, n):
    new = (temp[-1]**2)%m
    if(present[new]==-1):
        temp.append(new)
        present[new] = iter
    else:
        i = present[new]
        j = iter
        break
    

if(i!=-1):
    sum1 = sum(temp[:i])
    left = n-i
    sum2 = sum(temp[i:j])
    zz = j-i
    sum1+=sum2*(left//zz)
    still = left%zz
    while(still>0):
        sum1+=temp[i]
        i+=1


        still-=1
else:
    sum1 = sum(temp)
print(sum1)

Solution (Python):
n,x,m=map(int,input().split())
s=set()
p=[]
while x not in s:
  s.add(x)
  p+=[x]
  x=(x*x)%m
  if len(p)>=n:print(sum(p));quit()
r=b=t=v=0
a=[0]
for i in p:
  if i==x:b=1
  r+=1-b
  t+=b*i
  v+=i
  a+=[a[-1]+i]*b
l=len(p)
print(v+t*((n-l)//(l-r))+a[(n-l)%(l-r)])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,X,M = IL()

loop = [X]
flag = DD(int)
counter = 1
flag[X] = counter


while True:
  nX = (X*X)%M
  if flag[nX]:
    loop_begin = flag[nX]
    loop_length = len(loop)-loop_begin+1
    break
  else:
    counter += 1
    flag[nX] = counter
    loop.append(nX)
  X = nX


zenhan = sum(loop[:loop_begin-1])
kouhan = sum(loop[loop_begin-1:])

if N < loop_begin:
  print(sum(loop[:N]))
else:
  N -= loop_begin-1
  kaisu = (N-1)//loop_length
  amari = (N-1)%loop_length + 1
  print(zenhan + kaisu*kouhan + sum(loop[loop_begin-1:loop_begin-1+amari]))