AtCoder Beginner Contest 179 - Sequence Sum

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: MEDIUM

Starter code:

Solutions:
(n, x, m) = map(int, input().split())
yj = [x]
lps = 0
for i in range(n):
	an = yj[i] ** 2 % m
	if an in yj:
		lps = yj.index(an)
		break
	yj.append(an)
blp = yj[:lps]
lp = yj[lps:]
ans = sum(blp) + sum(lp) * ((n - len(blp)) // len(lp)) + sum(lp[:(n - len(blp)) % len(lp)])
print(ans)


(n, x, m) = map(int, input().split())
mod = [0] * m
mod[x % m] = 1
ans = x
for i in range(2, n + 1):
	x = x ** 2 % m
	if mod[x] == 0:
		ans += x
		mod[x] = i
	elif mod[x] == -1:
		break
	else:
		turn = i - mod[x]
		ans += x * ((n - i) // turn + 1)
		mod[x] = -1
print(ans)


(n, x, m) = map(int, input().split())
i = 0
a = x
aa = set()
aal = []
s = 0
while a not in aa:
	aa.add(a)
	aal.append(a)
	s += a
	i += 1
	if i == n:
		print(s)
		exit(0)
	a = a ** 2 % m
	if a == 0:
		print(s)
		exit(0)
st = aal.index(a)
cont = aal[st:]
nc = len(cont)
n -= st
ans = sum(aal[:st]) + sum(cont) * (n // nc) + sum(cont[:n % nc])
print(ans)


(n, x, m) = map(int, input().split())
amari = [x]
amariset = {x}
cnt = 0
p = 0
for i in range(n - 1):
	a = amari[-1] ** 2 % m
	if a in amariset:
		p = amari.index(a)
		cnt = i + 1 - p
		break
	else:
		amari.append(a)
		amariset.add(a)
if cnt == 0:
	print(sum(amari))
else:
	n -= len(amari)
	a = n // cnt
	b = n % cnt
	print(sum(amari) + a * sum(amari[p:]) + sum(amari[p:p + b]))


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) = map(int, input().split())
a = x
S = [0] * (m + 1)
F = [None] * m
F[x] = 0
(i0, j0) = (None, None)
for i in range(1, m + 1):
	S[i] = S[i - 1] + a
	a = pow(a, 2, m)
	if F[a] is not None:
		(i0, j0) = (F[a], i)
	F[a] = i
(q, r) = ((n - i0) // (j0 - i0), (n - i0) % (j0 - i0))
print((S[j0] - S[i0]) * q + S[i0 + r])


class DoublingAggregation:

	def __init__(self, nexts, arr, max_n, op, e):
		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])
				dat_next.append(op(d, dat[p]))
			self.table.append(perm_next)
			self.data.append(dat_next)

	def prod(self, 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):
		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) = map(int, input().split())
y = x
A = []
A.append(y)
cnt = 1
su = x
for i in range(m):
	y = y ** 2 % m
	cnt += 1
	if y in A:
		break
	else:
		A.append(y)
		su += y
c = A.index(y)
d = cnt - (c + 1)
e = sum(A[:c])
f = sum(A[c:c + (n - c) % d])
g = su - e
h = g * ((n - c) // d)
print(e + h + f)


(n, x, m) = map(int, input().split())
ans = x
b = x
box = [x]
c = 0
for i in range(1, n):
	b = b ** 2 % m
	if b == 0:
		print(ans)
		exit()
	if b in box:
		c = box.index(b)
		break
	ans += b
	box.append(b)
print(sum(box[:c]) + sum(box[c:]) * ((n - c) // len(box[c:])) + sum(box[c:c + (n - c) % len(box[c:])]))


(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) = list(map(int, input().split()))
r = [0] * m
r[x] = 1
a = x
t = 0
u = 0
s = [0, x]
for i in range(2, m + 2):
	a = a ** 2 % m
	s.append(s[-1] + a)
	if r[a] == 0:
		r[a] = i
	else:
		t = i - r[a]
		u = r[a]
		break
if u >= n:
	print(s[n])
else:
	p = (n - (u - 1)) // t
	q = (n - (u - 1)) % t
	ans = s[u - 1 + q] + p * (s[u + t] - s[u])
	print(ans)


(n, x, mod) = map(int, input().split())
d = [-1] * mod
ans = 0
syu = 0
al = []
for i in range(n):
	if d[x] != -1:
		en = i
		syu = i - d[x]
		break
	ans += x
	al.append(x)
	d[x] = i
	x = x * x % mod
if syu == 0:
	print(ans)
	exit()
ans += (n - en) // syu * sum(al[d[x]:en])
for i in range((n - en) % syu):
	ans += x % mod
	x = x * x % mod
print(ans)


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


(N, X, M) = map(int, input().split())
seen = [-2] * M
seen[X]
A = [X]
i = 1
while i < N:
	T = A[-1] ** 2 % M
	if seen[T] != -2:
		Roop = i - seen[T]
		(Left, Right) = (seen[T], i)
		break
	A.append(T)
	seen[T] = i
	i += 1
if i == N:
	print(sum(A))
	exit()
Roopsum = 0
for i in range(Left, Right):
	Roopsum += A[i]
Rest = N - len(A)
ans = sum(A)
ans += Rest // Roop * Roopsum
for i in range(Rest % Roop):
	ans += T
	T = T ** 2 % M
print(ans)


(N, X, M) = map(int, input().split())
hist = [-1] * (M + 1)
ans = X
hist[X] = 0
A = [X]
r = X % M
i = 1
N -= 1
while N:
	nxt = r * r % M
	if hist[nxt] != -1:
		break
	ans += nxt
	hist[nxt] = i
	A.append(nxt)
	i += 1
	r = nxt
	N -= 1
if N:
	A_sub = A[hist[nxt]:]
	L = len(A_sub)
	(q, rem) = divmod(N, L)
	ans += sum(A_sub) * q + sum(A_sub[:rem])
print(ans)


(n, x, m) = map(int, input().split())
chk = [0 for i in range(m)]
a = x
s = x
c = 0
ary = [x]
flg = False
while True:
	if c == n:
		break
	x = x ** 2 % m
	s += x
	c += 1
	if chk[x]:
		flg = True
		break
	ary.append(x)
	chk[x] = c
if flg == False:
	print(sum(ary[:-1]))
	exit()
cyc = ary[chk[x]:]
l1 = len(cyc)
ss = ary[:chk[x]]
l2 = len(ss)
tot = sum(ss) + sum(cyc) * ((n - l2) // l1) + sum(cyc[:(n - l2) % l1])
print(tot)


(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)]))


(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()))
(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)


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())
order = []
hist = [0] * M
for i in range(N):
	if hist[X]:
		j = order.index(X)
		rem = N - i
		(d, m) = divmod(rem, i - j)
		for k in order[j:]:
			hist[k] += d
		for k in order[j:j + m]:
			hist[k] += 1
		break
	order.append(X)
	hist[X] += 1
	X = X * X % M
ans = 0
for (i, h) in enumerate(hist):
	ans += i * h
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)


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()


(N, X, M) = map(int, input().split())
ans = 0
C = [0]
Xd = [-1] * (M + 1)
for i in range(N):
	x = X if i == 0 else x ** 2 % M
	if Xd[x] > -1:
		break
	Xd[x] = i
	ans += x
	C.append(ans)
loop_len = i - Xd[x]
if loop_len > 0:
	S = C[i] - C[Xd[x]]
	loop_num = (N - i) // loop_len
	ans += loop_num * S
	m = N - loop_num * loop_len - i
	ans += C[Xd[x] + m] - C[Xd[x]]
print(ans)


(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) = map(int, input().split())
(num, lst) = (set(), [])
for i in range(n):
	(num.add(x), lst.append(x))
	x = x ** 2 % m
	if x in num:
		(cnt, idx) = (i + 1, lst.index(x))
		break
ans = sum(num)
if x in num:
	(div, mod) = divmod(n - cnt, len(lst) - idx)
	ans += sum(lst[idx:]) * div
	ans += sum(lst[idx:idx + mod])
print(ans)


(N, X, M) = map(int, input().split())
A = [0] * (M + 1)
A[0] = X
D = [0] * (M + 1)
s = N
for i in range(1, N):
	a = A[i - 1] ** 2 % M
	if D[a] == 1:
		s = A.index(a)
		break
	else:
		A[i] = a
		D[a] = 1
if s == N:
	ans = sum(A)
else:
	A = A[:i]
	ans = 0
	l = len(A) - s
	ans += sum(A[:s])
	S = sum(A[s:])
	T = (N - s) // l
	ans += T * S
	K = N - s - l * T
	ans += sum(A[s:s + K])
print(ans)


(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())
sm = [-1 for i in range(m)] + [0]
w = [-1 for i in range(m)]
d = [m]
a = x
t = 0
s = 0
while True:
	s += a
	if w[a] != -1:
		inter = t - w[a]
		fv = w[a]
		ls = d[(n - fv) % inter + fv]
		lls = d[w[a]]
		print(sm[lls] + (n - fv) // inter * (s - sm[a]) + (sm[ls] - sm[lls]))
		break
	w[a] = t
	d.append(a)
	sm[a] = s
	t += 1
	a = a * a % m


(n, x, m) = map(int, input().split())
a = x
r = [False for _ in range(m)]
s = []
i = 0
while r[a] == False and i < n:
	r[a] = True
	s.append(a)
	a = pow(a, 2, m)
	i += 1
if i == n:
	ans = sum(s)
else:
	ai = s.index(a)
	c = (n - len(s)) // (len(s) - ai)
	d = n - len(s) - (len(s) - ai) * c
	ans = sum(s) + sum(s[ai:]) * c + sum(s[ai:ai + d])
print(ans)


(n, x, m) = map(int, input().split())
a = x
ans = a
flg = [0] * m
flg[a] = 1
l = [a]
lp = -1
for i in range(1, n):
	tmp = a * a % m
	a = tmp
	if flg[a] == 1:
		lp = l.index(a)
		break
	else:
		ans += tmp
		l.append(a)
		flg[a] = 1
if lp != -1:
	l2 = l[lp:]
	tmp = sum(l2)
	b = (n - len(l)) // len(l2)
	c = n - len(l) - b * len(l2)
	ans = ans + b * tmp + sum(l2[:c])
print(ans)


(N, X, M) = [int(x) for x in input().split()]
s = [0] * (M + 10)
s[1] = X
d = {X: 0}
tmp = X
for i in range(M):
	tmp = tmp * tmp % M
	if tmp == 0:
		print(s[i + 1])
		exit()
	elif tmp in d:
		(l, r) = (d[tmp], i + 1)
		sl = s[r] - s[l]
		loop = r - l
		ans = sl * ((N - l) // loop) + s[l + (N - l) % loop]
		print(ans)
		exit()
	else:
		d[tmp] = i + 1
		s[i + 2] = s[i + 1] + tmp
print(d)


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

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()


(n, x, m) = map(int, input().split())
a = [x]
su = x
s = {x}
for i in range(n - 1):
	x = x ** 2 % m
	if x in s:
		n -= i + 1
		a = a[a.index(x):]
		l = len(a)
		su += sum(a) * (n // l)
		n -= n // l * l
		su += sum(a[:n])
		print(su)
		exit()
	a.append(x)
	su += x
	s.add(x)
print(su)


import math
(n, x, m) = list(map(int, input().split()))
appearance = {}
sequence = []
a = x
loopExists = False
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)
	loopCount = (n - preLoopLength) // loopLength
	restLength = (n - preLoopLength) % loopLength
	preLoopTotal = sum(preLoopNums)
	loopTotal = sum(loopNums)
	restTotal = sum(loopNums[:restLength])
	total = preLoopTotal + loopTotal * loopCount + restTotal
	print(total)


import sys
input = sys.stdin.readline
(N, X, M) = map(int, input().split())
table = [0] * M
c = [0] * M
c[X] = 1
x = X
while table[x] <= 1:
	table[x] += 1
	if c[x ** 2 % M] == 0:
		c[x ** 2 % M] = c[x] + 1
	x = x ** 2 % M
loop = table.count(2)
res = 0
for x in range(M):
	if c[x] in range(1, N + 1):
		res += x
		if c[x] + loop in range(1, N + 1) and table[x] >= 2:
			res += x * ((N - c[x]) // loop)
print(res)


(n, x, m) = map(int, input().split())
tt = [i * i % m for i in range(m)]
ss = [i for i in range(m)]

def merge(to1, s1, to2, s2):
	to3 = [to2[to1[i]] for i in range(m)]
	s3 = [s1[i] + s2[to1[i]] for i in range(m)]
	return (to3, s3)
t = [i for i in range(m)]
s = [0] * m
while n:
	if n % 2 == 1:
		(t, s) = merge(t, s, tt, ss)
	(tt, ss) = merge(tt, ss, tt, ss)
	n //= 2
print(s[x])


(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())
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())
ans = []
flag = False
for i in range(n):
	if x in ans:
		v = x
		flag = True
		break
	ans.append(x)
	x = x ** 2 % m
if flag:
	p = ans.index(v)
	l = len(ans) - p
	(d, e) = divmod(n - p, l)
	print(sum(ans[:p]) + d * sum(ans[p:]) + sum(ans[p:p + e]))
else:
	print(sum(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())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
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)
		exit()
	P.append(sum_p)
	sum_p += x
	X[x] = i
	x = x * x % m
print(sum_p)


(N, X, M) = [int(_) for _ in input().split()]
seen = {}
i = 0
A = []
while True:
	if X in seen:
		i2 = seen[X]
		i3 = i
		break
	seen[X] = i
	A += [X]
	i += 1
	X = X ** 2 % M
if N < i3:
	ans = sum(A[:N])
elif i2 == i3:
	ans = sum(A[:i2]) + A[i2] * (N - i2)
else:
	(q, r) = divmod(N - i2, i3 - i2)
	ans = sum(A[:i2]) + sum(A[i2:]) * q + sum(A[i2:i2 + r])
print(ans)


(n, x, m) = list(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]
		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)


(N, X, M) = map(int, input().split())
pt = [[0] * (M + 100) for i in range(70)]
to = [[0] * (M + 100) for i in range(70)]
for i in range(M + 1):
	to[0][i] = i * i % M
	pt[0][i] = i
for i in range(65):
	for j in range(M + 1):
		to[i + 1][j] = to[i][to[i][j]]
		pt[i + 1][j] = pt[i][j] + pt[i][to[i][j]]
ans = 0
for i in range(60):
	if N >> i & 1:
		ans += pt[i][X]
		X = to[i][X]
print(ans)


(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())
a = []
check = [-1] * m
i = 0
while check[x] == -1:
	a.append(x)
	check[x] = i
	x = x * x % m
	i += 1
if n <= i:
	print(sum(a[:n]))
else:
	print(sum(a[:check[x]]) + (n - check[x]) // (i - check[x]) * sum(a[check[x]:]) + sum(a[check[x]:check[x] + (n - check[x]) % (i - check[x])]))


(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()))
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1:
	X[x] = len(P)
	P.append(sum_p)
	sum_p += x
	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) = map(int, input().split())
arr = [x]
s = set()
s.add(x)
h = -1
r = 0
for i in range(n - 1):
	val = arr[-1] ** 2 % m
	if val not in s:
		arr += [arr[-1] ** 2 % m]
		s.add(arr[-1])
	else:
		h = i
		r = val
		break
res = sum(arr)
if h != -1:
	new_arr = arr[arr.index(r):]
	rest = n - (h + 1)
	c = len(new_arr)
	q = rest // c
	ssum = sum(new_arr) * q
	r = rest % c
	for i in range(r):
		ssum += new_arr[i]
	res += ssum
print(res)


(N, X, M) = list(map(int, input().split()))
memo = [0] * (2 * M + 1)
val_idx = {X: 1}
seen = set([X])
memo[1] = X
loop_length = 0
for i in range(2, N + 1):
	X = X ** 2 % M
	if X not in seen:
		seen.add(X)
		val_idx[X] = i
		memo[i] += memo[i - 1] + X
	else:
		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())
id = [-1] * M
a = []
l = 0
tot = 0
while id[X] == -1:
	a.append(X)
	id[X] = l
	l += 1
	tot += X
	X = X ** 2 % M
c = l - id[X]
s = 0
for i in range(id[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 * (N // c)
	N %= c
	for i in range(N):
		ans += a[id[X] + i]
print(ans)


(N, X, M) = map(int, input().split())
visited = [(-1, -1)] * M
ans = 0
for i in range(N):
	if visited[X][0] >= 0:
		d = ans - visited[X][0]
		left = N - i
		length = i - visited[X][1]
		ans += left // length * d
		left %= length
		for j in range(left):
			ans += X
			X = X * X % M
		break
	visited[X] = (ans, i)
	ans += X
	X = X * X % M
print(ans)


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()))
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)


(N, X, M) = map(int, input().split())
if X == 0:
	print(0)
	exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
	tl.append(tx)
	ts.add(tx)
	tx = pow(tx, 2, M)
	if tx in ts:
		ttl = tl[tl.index(tx):]
		break
ans = sum(tl)
if len(ttl) > 0:
	(d, m) = divmod(N - len(tl), len(ttl))
	ans += sum(ttl) * d + sum(ttl[:m])
print(ans)


(n, x, m) = map(int, input().split())
ans = x
num = 0
l = [0] * m
lis = [-1] * m
l[0] = x
lis[x] = num
for i in range(1, n):
	x = x * x % m
	num += 1
	if lis[x] != -1:
		a = (n - i) // (i - lis[x])
		b = (n - i) % (i - lis[x])
		ans += a * sum(l[lis[x]:i])
		for j in range(lis[x], lis[x] + b):
			ans += l[j]
		break
	l[i] = x
	lis[x] = i
	ans += x
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()))
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) = 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])


(n, x, m) = map(int, input().split())
l = [-1] * m
s = [0] * m
t = p = 0
while l[x] < 0:
	t += 1
	l[x] = t
	s[x] = s[p] + x
	p = x
	x = pow(p, 2, m)
T = t + 1 - l[x]
S = s[p] + x - s[x]
if n < l[x]:
	print(s[l.index(n)])
else:
	print(S * ((n - l[x]) // T) + s[l.index(l[x] + (n - l[x]) % T)])


(N, X, M) = map(int, input().split())
L = [X]
S = set([X])
idx = N
MOD = 10 ** 9 + 7
for i in range(1, N):
	X = X ** 2 % M
	if len(S) != len(L):
		idx = L.index(X)
		break
	L.append(X)
	S.add(X)
if idx == N:
	print(sum(L[:idx]))
else:
	k = (N - idx) % len(L[idx:])
	print(sum(L[:idx]) + (N - idx) // len(L[idx:]) * sum(L[idx:]) + sum(L[idx:idx + k]))


(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]))


(n, x, m) = map(int, input().split())
f = [-1] * m
ans = x
n -= 1
while n > 0:
	if f[x] == -1:
		f[x] = pow(x, 2, m)
		ans += f[x]
		x = f[x]
		n -= 1
	else:
		break
loop = [x]
ans -= x
for i in range(n):
	tmp = pow(loop[-1], 2, m)
	if tmp == loop[0]:
		break
	loop.append(tmp)
loopsum = sum(loop)
ans += (n + 1) // len(loop) * loopsum + sum(loop[0:(n + 1) % len(loop)])
print(ans)


import sys
readline = sys.stdin.readline
(N, X, M) = map(int, readline().split())
nex = [0] * M
sums = [0] * M
for i in range(M):
	nex[i] = i * i % M
	sums[i] = i
ans = 0
while N:
	if N & 1:
		ans += sums[X]
		X = nex[X]
	sums = [sums[i] + sums[nex[i]] for i in range(M)]
	nex = [nex[nex[i]] for i in range(M)]
	N >>= 1
print(ans)


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()))

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)
	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)


import math
import sys
pin = sys.stdin.readline

def main():
	(N, X, M) = map(int, pin().split())
	A = X
	d = [X]
	su = X
	for i in range(N - 1):
		A = A ** 2 % M
		if A in d:
			t = d.index(A)
			T = N - i - 1
			d = d[t:]
			l = len(d)
			su += sum(d) * (T // l)
			T = T % (T // l)
			su += sum(d[:T])
			print(su)
			return
		d.append(A)
		su += A
	print(su)
	return
main()


(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)


(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]))


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


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)
l = LIST.index(a * a % M)
LEN = len(LIST)
if N <= LEN:
	print(sum(LIST[:N]))
else:
	ANS = sum(LIST[:l])
	N -= l
	LIST = LIST[l:]
	S = sum(LIST)
	(r, q) = divmod(N, len(LIST))
	print(ANS + S * r + sum(LIST[:q]))


(n, x, m) = map(int, input().split())
num = {x}
num2 = [x]
while True:
	temp = num2[-1] ** 2 % m
	if temp in num:
		break
	else:
		num.add(temp)
		num2.append(temp)
temp2 = num2.index(temp)
num3 = num2[:temp2]
num4 = num2[temp2:]
ans = sum(num3) + sum(num4) * ((n - len(num3)) // len(num4)) + sum(num4[:(n - len(num3)) % len(num4)])
print(ans)


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


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, x, m) = map(int, input().split())
s = set([x])
l = [x]
for i in range(m):
	x = x ** 2 % m
	if x in s:
		start_index = l.index(x)
		break
	else:
		s.add(x)
		l.append(x)
ans = sum(l[:start_index])
q = l[start_index:]
p = (n - start_index) // len(q)
ans += sum(q) * p
ans += sum(q[:n - p * len(q) - start_index])
print(ans)


(n, x, m) = map(int, input().split())
g = x * 1
ans = x
arr = []
res = set([])
loop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		loop = (i, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp
for (i, y) in enumerate(arr):
	if y == loop[1]:
		k = i
		break
ini = g + sum(arr[:k])
mul = ans - ini
(t, v) = divmod(n - k - 1, loop[0] - k)
print(ini + mul * t + sum(arr[k:k + v]))


(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)
ans = sum(loop_bef) + sum(loop) * loop_num + sum(loop[:after_loop])
print(ans)


(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


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)
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())
k = x
L = list()
c = dict()
for i in range(M):
	if i == N:
		print(sum(L))
		exit()
	if x == 0:
		print(sum(L))
		exit()
	L.append(x)
	x = x * x % M
	if x in c:
		q = x
		break
	c[x] = 1
moto = sum(L)
N -= len(L)
for i in range(len(L)):
	if L[i] == q:
		roop = list(L[i:])
L = roop
a = len(L)
if N % a == 0:
	print(moto + sum(L) * (N // a))
else:
	s = N // a
	t = N % a
	ans = sum(L) * s
	ans += sum(roop[:t])
	print(moto + ans)


(n, x, m) = map(int, input().split())
ans = x
rp = [x]
if n <= m:
	for i in range(n - 1):
		x = pow(x, 2, m)
		ans += x
	print(ans)
	exit()
for i in range(m + 1):
	x = pow(x, 2, m)
	if x in rp:
		tt = rp.index(x)
		t = len(rp) - tt
		break
	else:
		rp.append(x)
tmp = sum(rp[tt:])
wari = (n - tt) // t
amari = (n - tt) % t
ans = sum(rp[:tt]) + tmp * wari + sum(rp[tt:tt + amari])
print(ans)


(N, X, M) = map(int, input().split())
m = [0] * M
t = {}

def f(x, y):
	return x * x % y
a = X
s = 0
for i in range(N):
	if a in t:
		x = t[a]
		nn = N - x
		(q, r) = divmod(nn, i - x)
		s = m[x - 1] + (m[i - 1] - m[x - 1]) * q + m[x - 1 + r] - m[x - 1]
		break
	t[a] = i
	s += a
	m[i] = s
	a = f(a, M)
print(s)


(N, X, M) = map(int, input().split())
A = [X]
S = [0, X]
Y = [-1] * M
f = 0
s = X
for i in range(1, M * 5 + 10):
	a = A[-1] ** 2 % M
	s += a
	A.append(a)
	S.append(s)
	if f == 0 and Y[a] >= 0:
		rp = i - Y[a]
		t = Y[a]
		f = 1
	Y[a] = i
if N < M * 5 * 0:
	print(S[N])
else:
	j = N % rp + (t // rp + 1) * rp
	print(S[j] + (S[t + rp] - S[t]) * (N - j) // rp)


(N, X, M) = map(int, input().split())
d = dict()
L = []
for i in range(M + 1):
	if X not in d:
		d[X] = i
		L.append(X)
	else:
		j = d[X]
		k = i
		break
	X = X * X % M
s = k - j
(kk, zz) = divmod(N - j, s)
print(sum(L[:j]) + sum(L[j:]) * kk + sum(L[j:j + zz]))


(N, X, M) = map(int, input().split())
i = X % M
L = [i]
S = set([i])
i = i ** 2 % M
while not i in S:
	L.append(i)
	S.add(i)
	i = i ** 2 % M
index = L.index(i)
k = (N - index) // len(L[index:])
l = (N - index) % len(L[index:])
ans = sum(L[:index]) + (k * sum(L[index:]) + sum(L[index:index + l]))
print(ans)


(n, x, m) = map(int, input().split())
alist = []
blist = [0] * m
num = x % m
while blist[num] == 0:
	alist.append(num)
	blist[num] = 1
	num = num ** 2 % m
num1 = alist.index(num)
num2 = len(alist)
if x == 1:
	print(n)
elif n <= num1:
	print(sum(alist[0:n]))
else:
	cycle = (n - num1) // (num2 - num1)
	print(sum(alist[0:num1]) + cycle * sum(alist[num1:num2 + 1]) + sum(alist[num1:n - cycle * (num2 - num1)]))


(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)


(n, x, m) = map(int, input().split())
arr = [x]
mod = x
memo = [-1 for _ in range(m + 1)]
ans = 0
for i in range(1, n):
	mod = mod ** 2 % m
	idx = memo[mod]
	if idx != -1:
		a = i - idx
		(q, _mod) = divmod(n - idx, a)
		ans = sum(arr[0:idx]) + q * sum(arr[idx:idx + a]) + sum(arr[idx:idx + _mod])
		break
	arr.append(mod)
	memo[mod] = i
if ans == 0:
	ans = sum(arr)
print(ans)


(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)


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())
i = int(2)
a = [x]
q = int(0)
while i <= n and q == 0:
	x = x ** 2 % m
	if x in a:
		q = 1
	else:
		a.append(x)
	i = i + 1
if len(a) == n:
	print(sum(a))
else:
	j = a.index(x)
	b = a[0:j]
	c = a[j:]
	lb = len(b)
	lc = len(c)
	k = (n - lb) % lc
	l = (n - lb) // lc
	d = c[0:k]
	print(sum(b) + sum(c) * l + sum(d))


(n, x, m) = map(int, input().split())
ans = 0
al = set([x])
for i in range(n):
	ans += x
	x = x ** 2 % m
	if x == 0:
		break
	if x in al:
		ind = list(al).index(x)
		loop = i - ind + 1
		l = list(al)
		ans += sum(l[ind:i + 1]) * ((n - i - 1) // loop)
		for j in range((n - i - 1) % loop):
			ans += l[ind + j]
		break
	al.add(x)
print(ans)


(n, x, m) = map(int, input().split())
S = [0]
F = [None] * m
for i in range(m + 1):
	S.append(S[-1] + x)
	if F[x] is not None:
		j = F[x]
		(q, r) = ((n - j) // (i - j), (n - j) % (i - j))
		print((S[i] - S[j]) * q + S[j + r])
		exit()
	F[x] = i
	x = pow(x, 2, m)
print(0)


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):
	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] = j * j % M
		S[0][j] = j
	for i in range(0, D - 1):
		for j in range(M):
			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())
ls = [X]
for i in range(M):
	Ai = ls[-1] ** 2 % M
	if Ai in ls:
		loop = ls[ls.index(Ai):]
		lenloop = len(loop)
		sumloop = sum(loop)
		startls = ls[:ls.index(Ai)]
		break
	ls.append(Ai)
if N <= len(startls):
	ans = sum(startls[:N])
else:
	ans = sum(startls) + (N - len(startls)) // lenloop * sumloop + sum(loop[:(N - len(startls)) % lenloop])
print(ans)


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])


(N, X, M) = map(int, input().split())
acc = [0]
S = dict()
Ai = X
i = 0
while Ai not in S:
	S[Ai] = i
	acc.append(acc[-1] + Ai)
	i += 1
	Ai = Ai * Ai % M
t = S[Ai]
T = i - t
if N <= t:
	ans = acc[N]
else:
	ans = acc[t] + (acc[-1] - acc[t]) * ((N - t) // T)
	if (N - t) % T > 0:
		ans += acc[(N - t) % T + t] - acc[t]
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()
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]
		break
	aa.append(x)
	pos[x] = i
	x = pow(x, 2, md)
cs = sum(aa[p:])
if n <= len(aa):
	print(sum(aa[:n]))
	return
n -= p
cnt = n // c
n %= c
n += p
print(cs * cnt + sum(aa[:n]))


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
	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)
			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]
	else:
		ans -= A[-1]
	return ans
print(solve1(n, x, m))


(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
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(ans)


import sys
(n, x, m) = (int(i) for i in input().split())
l = [x]
ans = x
memo_array = [-1] * (m + 1)
for i in range(1, n):
	ans = ans ** 2 % m
	idx = memo_array[ans]
	if idx != -1:
		(loop_num, mod) = divmod(n - idx, i - idx)
		print(sum(l[:idx]) + sum(l[idx:]) * loop_num + sum(l[idx:idx + mod]))
		sys.exit()
	l.append(ans)
	memo_array[ans] = i
print(sum(l))


(N, X, M) = map(int, input().split())
array = [0, X]
array2 = [X]
a = X
sum = X
valid = True
while True:
	a = pow(a, 2, M)
	if a in array2:
		y = array2.index(a)
		break
	sum += a
	array.append(sum)
	array2.append(a)
l = len(array2)
h = l - y
if N <= y:
	print(array[N])
else:
	ans = array[y] + (array[-1] - array[y]) * ((N - y) // h) + array[y + (N - y) % h] - array[y]
	print(ans)


(n, x, m) = map(int, input().split())
a = x
li = [a]
exists = dict()
i = 1
for i in range(2, n + 1):
	a = a * a % m
	if a in exists:
		break
	li.append(a)
	exists[a] = i
ans = sum(li)
if i != n:
	(loop, left) = divmod(n - i + 1, i - exists[a])
	ans += loop * sum(li[exists[a] - 1:]) + sum(li[exists[a] - 1:exists[a] - 1 + left])
print(ans)


(n, x, m) = map(int, input().split())
a = [-1] * 10 ** 5
a[x % m] == 0
b = [x % m]
for i in range(1, n):
	x = x ** 2 % m
	if a[x % m] == -1:
		a[x % m] = i
		b.append(b[-1] + x % m)
	else:
		s = a[x % m] - 1
		g = i - 1
		print((b[g] - b[s]) * ((n - s - 1) // (g - s)) + b[s + (n - s - 1) % (g - s)])
		break
else:
	print(b[-1])


(N, X, M) = map(int, input().split())
lst = []
(n, s) = (X, 0)
for i in range(N):
	if n in lst:
		break
	lst.append(n)
	n = n * n % M
if len(lst) < N:
	k = lst.index(n)
	s1 = sum(lst[:k])
	s2 = sum(lst[k:]) * ((N - k) // (len(lst) - k))
	s3 = sum(lst[k:k + (N - k) % (len(lst) - k)])
	s = s1 + s2 + s3
else:
	s = sum(lst)
print(s)


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

def am(a, b):
	return a * a % b
l = [x]
u = []
now = x
for i in range(n):
	s = am(now, m)
	if s in l:
		break
	l.append(s)
	now = s
c = l.index(s)
k = 0
if 0 in l:
	print(sum(l))
else:
	for i in range(c):
		u.append(l.pop(0))
	a = (n - len(u)) // len(l)
	b = (n - len(u)) % len(l)
	print(sum(u) + a * sum(l) + sum(l[:b]))


(N, X, M) = map(int, input().split())
A = [X]
for i in range(1, M + 1):
	d = pow(A[i - 1], 2, M)
	if d in A:
		break
	A.append(d)
c = A.index(d)
e = len(A)
cy = e - c
ans = 0
if N <= e:
	for i in range(N):
		ans += A[i]
	print(ans)
else:
	m = sum(A[:c])
	n = sum(A[c:e])
	f = (N - c) // cy
	ans = m + n * f + sum(A[c:c + (N - c) % cy])
	print(ans)


(n, x, m) = map(int, input().split())
ans = x
a = x
res = [x]
res2 = 0
r = 0
for i in range(1, m + 1):
	a = a * a % m
	if a == 0:
		break
	if a in res:
		r = res.index(a)
		res2 = i - r
		break
	else:
		ans += a
		res.append(a)
b = [0] * m
for i in range(res2):
	b[i + 1] = b[i] + res[r + i]
if res2 == 0:
	print(ans)
else:
	k = (n - r) // res2
	l = (n - r) % res2
	ans += b[res2] * (k - 1) + b[l]
	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) = map(int, input().split())
ans = 0
a = [0]
id = [0] * (m + 1)
l = 1
while id[x] == 0:
	a.append(x)
	id[x] = l
	ans += x
	l += 1
	x = x ** 2 % m
c = l - id[x]
s = 0
for i in range(id[x], l):
	s += a[i]
if n <= l - 1:
	ans = 0
	for i in range(1, n + 1):
		ans += a[i]
else:
	n -= l
	n += 1
	ans += s * (n // c)
	n %= c
	for i in range(n):
		ans += a[id[x] + i]
print(ans)


(N, X, M) = list(map(int, input().split()))
i = 1
a = X
s = 0
L = []
while i < N and a > 0:
	L.append(a)
	s += a
	a = a ** 2 % M
	if a in L:
		j = L.index(a)
		break
	i += 1
else:
	s += a
	print(s)
	exit()
t = sum(L[:j])
L = L[j:]
u = s - t
N = N - j
v = t + u * (N // (i - j))
if N % (i - j) == 0:
	pass
else:
	v += sum(L[:N % (i - j)])
print(v)


(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())
dp = [x]
s = set([x])
for i in range(1000000):
	if dp[-1] ** 2 % m in s:
		dp.append(dp[-1] ** 2 % m)
		break
	s.add(dp[-1] ** 2 % m)
	dp.append(dp[-1] ** 2 % m)
ind = dp.index(dp[-1])
del dp[-1]
print(sum(dp[:ind]) + sum(dp[ind:]) * ((n - ind) // (len(dp) - ind)) + sum(dp[ind:ind + (n - ind) % (len(dp) - ind)]))


(n, x, m) = 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)


(n, x, m) = [int(x) for x in input().split()]
A = [x]
while len(A) < n:
	a = A[-1] * A[-1] % m
	if a not in A:
		A.append(a)
	else:
		i = A.index(a)
		loop_len = len(A) - i
		print(sum(A[:i]) + sum(A[i:]) * ((n - i) // loop_len) + sum(A[i:i + (n - i) % loop_len]))
		break
else:
	print(sum(A))


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

def f(x, m):
	return x % m
a = x
a_set = {a}
a_array = [a]
a_index = 0
while True:
	a = f(a ** 2, m)
	if a in a_set:
		a_index = a_array.index(a)
		break
	a_set.add(a)
	a_array.append(a)
a_iter_array = a_array[a_index:]
(div, mod) = divmod(n - a_index, len(a_iter_array))
ans = sum(a_array[:a_index]) + sum(a_iter_array) * div + sum(a_iter_array[:mod])
print(ans)


(n, x, m) = map(int, input().split())
A = [x]
where = {x: 0}
a = x
for i in range(1, n):
	a = A[-1] ** 2 % m
	if a in where:
		break
	where[a] = i
	A.append(a)
perstart = where[a]
res = sum(A)
rem = n - len(A)
per = len(A) - perstart
res += rem // per * sum(A[perstart:perstart + per])
res += sum(A[perstart:perstart + rem % per])
print(res)


(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())
tmp = []
while True:
	tmp.append(x)
	x = pow(x, 2, m)
	if x in tmp:
		break
k = 0
while True:
	if tmp[k] == x:
		break
	k += 1
if k > n:
	print(sum(tmp[:n]))
else:
	t = k
	a = (n - k) // (len(tmp) - k)
	s = (n - k) % (len(tmp) - k)
	print(sum(tmp[:k]) + sum(tmp[k:]) * a + sum(tmp[k:k + s]))


(N, X, M) = map(int, input().split())
Flag = [True] * M
A = []
temp = X
while Flag[temp]:
	A.append(temp)
	Flag[temp] = False
	temp = temp ** 2 % M
	last = temp
I = A.index(last)
looplen = len(A) - I
(loop, cnt) = divmod(max(N - I, 0), looplen)
ans = 0
if N <= I + 1:
	ans += sum(A[:N])
else:
	ans += sum(A[:I])
	ans += loop * sum(A[I:])
	ans += sum(A[I:I + cnt])
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())

def f(x, m):
	return x ** 2 % m
check = [False for _ in range(M)]
d = [X]
max_x = 0
for _ in range(1, N + 1):
	X = f(X, M)
	if check[X]:
		break
	else:
		check[X] = True
	d.append(X)
idx = d.index(X)
ans = sum(d[:idx])
N -= idx
d = d[idx:]
sumd = sum(d)
ans += N // len(d) * sumd
ans += sum(d[:N % len(d)])
print(ans)


(N, X, M) = map(int, input().split())
s = 0
mt = []

def f(x):
	return x ** 2 % M
i = 0
while True:
	i += 1
	mt.append(X)
	a = f(X)
	if i == N:
		f = 1
		break
	elif a in mt:
		f = 0
		break
	else:
		X = a
if f == 1:
	print(sum(mt))
else:
	e = mt.index(a)
	s1 = mt[:e]
	s2 = mt[e:]
	l = i - e
	(c, d) = divmod(N - e, l)
	print(sum(s1) + sum(s2) * c + sum(s2[:d]))


def main():
	(N, X, M) = map(int, input().split())
	Set = {X}
	A = [X]
	for i in range(1, M + 1):
		nextA = A[i - 1] ** 2 % M
		if nextA in Set:
			loop = A[A.index(nextA):]
			break
		else:
			Set.add(nextA)
			A.append(nextA)
	lenloop = len(loop)
	(x, y) = divmod(N - len(A), lenloop)
	ans = sum(A) + x * sum(loop) + sum(loop[0:y])
	print(ans)
main()


import sys
readline = sys.stdin.readline

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) = map(int, input().split())
loop = []
loop.append(x)
looplist = [0] * m
looplist[x] = 1
for i in range(1, m + 1):
	x = x ** 2 % m
	if looplist[x] == 0:
		looplist[x] = 1
		loop.append(x)
	else:
		break
ss = loop.index(x)
amari = loop[:ss]
neoloop = loop[ss:]
lon = len(neoloop)
if n <= ss:
	print(sum(amari[:n]))
else:
	print(sum(amari) + (n - ss) // lon * sum(neoloop) + sum(neoloop[:(n - ss) % lon]))


(N, X, M) = map(int, input().split(' '))
q = [-1] * (M + 1)
A = X
i = 0
su = []
p1 = 0
p2 = 0
while q[A] == -1:
	q[A] = i
	su.append(A)
	A = A * A % M
	i += 1
if N == len(su):
	print(sum(su))
else:
	r = q[A]
	r2 = (N - r) % (i - r)
	ans1 = sum(su[0:r])
	ans2 = sum(su[r:r + r2])
	ans3 = sum(su[r:])
	print(ans1 + ans2 + ans3 * ((N - r) // (i - r)))


(N, X, M) = map(int, input().split())
if N == 1:
	print(X)
	exit()
a = [X]
sa = set([X])
for i in range(1, N):
	X = X ** 2 % M
	if X in sa:
		break
	else:
		a.append(X)
		sa.add(X)
if i == N - 1:
	print(sum(a))
	exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i - start
sets = (N - start) // rep
more = (N - start) % rep
ans += base * sets + sum(a[start:start + more])
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) = map(int, input().split())
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
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) = map(int, input().split())
A = [X]
A_dict = {X}
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0
for i in range(M + 1):
	a = a ** 2 % M
	if a in A_dict:
		r0 = A.index(a)
		l = len(A[r0:])
		r = (N - i - 1) // l
		amari = (N - i - 1) % l
		s = s + sum(A[r0:]) * r + sum(A[r0:r0 + amari])
		break
	A.append(a)
	A_dict.add(a)
	s += A[-1]
print(s)


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, M) = map(int, input().split())
A = [X]
x = A[0] ** 2 % M
i = 0
while not x in A:
	A.append(x)
	i += 1
	x = x ** 2 % M
loopid = A.index(x)
looplen = i - loopid + 1
loopsum = sum(A[loopid:])
startsum = sum(A[:loopid])
ans = 0
if N - 1 < loopid:
	ans = sum(A[:N])
else:
	loopnum = (N - 1 - loopid + 1) // looplen if looplen else N - 1 - loopid
	rest = N - 1 - (loopid + looplen * loopnum) + 1
	ans += startsum
	ans += loopnum * loopsum
	ans += sum(A[loopid:loopid + rest])
print(ans)


(n, x, m) = map(int, input().split())
tmp = [x]
while x ** 2 % m not in tmp:
	x = x ** 2 % m
	tmp.append(x)
cnt = len(tmp)
x = x ** 2 % m
if n <= cnt:
	print(sum(tmp[:n]))
	exit()
for i in range(len(tmp)):
	if tmp[i] == x:
		st = sum(tmp[:i])
		rp = tmp[i:]
		(div, mod) = divmod(n - i, len(rp))
		en = sum(rp[:mod])
		print(st + sum(rp) * div + en)
		exit()


(n, x, m) = map(int, input().split())
cnt = [x]
c = set()
c.add(x)
for i in range(m + 1):
	x = x * x % m
	if x in c:
		break
	cnt.append(x)
	c.add(x)
start = cnt.index(x)
ans = sum(cnt[:start])
roop = len(cnt) - start
n = n - start
ans = ans + n // roop * sum(cnt[start:]) + sum(list(cnt)[start:start + n % roop])
print(ans)


from collections import defaultdict
(N, X, M) = map(int, input().split())
cnt = 0
index = [X]
d = defaultdict(int)
i = 1
while True:
	X = pow(X, 2, M)
	if d[X] != 0:
		z = d[X]
		break
	d[X] = i
	i += 1
	index.append(X)
target = len(index) - z
total = 0
for i in range(z, len(index)):
	total += index[i]
for i in range(z):
	cnt += index[i]
total2 = 0
for i in range(z, z + (N - z) % target):
	total2 += index[i]
cnt += total * ((N - z) // target) + total2
print(cnt)


(n, x, m) = map(int, input().split())
a = list()
ans = 0
s = n
for i in range(n):
	ans += x
	a.append(x)
	x = x ** 2 % m
	if x in a:
		s = a.index(x)
		break
sum = 0
if s != n:
	for i in range(s, len(a)):
		sum += a[i]
if len(a) > s:
	ans += sum * ((n - s) // (len(a) - s) - 1)
	z = (n - s) % (len(a) - s)
	if z != 0:
		for i in range(z):
			ans += a[s + i]
print(ans)


(N, X, M) = map(int, input().split())
cur = X
pos = {}
path = []
i = 0
while cur not in pos:
	pos[cur] = i
	path.append(cur)
	cur = cur ** 2 % M
	i += 1
loop_start = pos[cur]
ans = None
if N <= len(path):
	ans = sum(path[:N])
else:
	ans = sum(path)
	left = N - len(path)
	(q, r) = divmod(left, len(path) - loop_start)
	ans += q * sum(path[loop_start:]) + sum(path[loop_start:loop_start + r])
print(ans)


(N, X, M) = map(int, input().split())
a = X
ls = [X]
point = N
for i in range(N):
	a = a * a % M
	if a in ls:
		point = ls.index(a)
		break
	else:
		ls.append(a)
initial = len(ls[:point])
cycle_len = len(ls[point:])
cycle_sum = sum(ls[point:])
cycles = (N - initial) // cycle_len
cycles_rem = (N - initial) % cycle_len
print(sum(ls[:point]) + cycles * cycle_sum + sum(ls[point:point + cycles_rem]))


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())
L = []
used = set()
while x not in used:
	used.add(x)
	L.append(x)
	x = x * x % m
cnt = 0
while L[cnt] != x:
	cnt += 1
l = len(L)
if n <= l:
	print(sum(L[:n]))
	exit()
s = sum(L)
t = sum(L[cnt:])
(q, r) = divmod(n - l, l - cnt)
ans = s + q * t
for i in range(r):
	ans += L[cnt]
	cnt += 1
print(ans)


(N, X, M) = map(int, input().split())
a = X
hist = [a]
indices = [-1] * M
indices[a] = 0
flag = 0
for i in range(1, min(10 ** 6, N)):
	a = a ** 2 % M
	if indices[a] != -1:
		idx = indices[a]
		flag = 1
		break
	hist.append(a)
	indices[a] = i
if flag == 0:
	print(sum(hist))
	exit()
cycle = hist[idx:]
margin = hist[:idx]
(q, r) = divmod(N - len(margin), len(cycle))
print(sum(margin) + sum(cycle) * q + sum(cycle[:r]))


def resolve():
	(n, x, m) = map(int, input().split())
	ans = x
	y = [x]
	for i in range(n - 1):
		x = x ** 2 % m
		if x not in y:
			y.append(x)
		else:
			break
	b = y.index(x)
	N = len(y[b:])
	c = sum(y[b:])
	ans = sum(y[:b]) + c * ((n - b) // N) + sum(y[b:b + (n - b) % N])
	print(ans)
resolve()


(N, X, M) = map(int, input().split())
table = [0] * (M + 1)
pre = X
table[pre] = 0
seq = [pre]
cnt = 0
while True:
	cnt += 1
	A = pre ** 2 % M
	if not table[A]:
		seq.append(A)
		table[A] = cnt
		pre = A
	else:
		f = table[A]
		s = cnt
		break
ans = 0
for i in range(f + (N - f) % (s - f)):
	ans += seq[i]
m = (N - f) // (s - f)
for i in range(f, s):
	ans += seq[i] * m
print(ans)


(n, x, m) = map(int, input().split())
a = []
mod_check_list = [False for _ in range(m)]
a.append(x * x % m)
ind = 0
s = 0
for i in range(m):
	t = a[i] * a[i] % m
	if mod_check_list[t]:
		ind = a.index(t)
		break
	mod_check_list[t] = True
	a.append(t)
s = sum(a[ind:])
l = len(a) - ind
loop_times = (n - 1 - ind) // l
answer = loop_times * s
for i in range((n - 1 - ind) % l):
	answer += a[i + ind]
print(answer + x + sum(a[:ind]))


(n, x, m) = map(int, input().split())
result = [x]
for i in range(m):
	y = result[-1] * result[-1] % m
	if y in result:
		start = result.index(y)
		end = i
		break
	result.append(y)
loop = result[start:]
a = start
b = (n - a) // len(loop)
c = (n - a) % len(loop)
ans = sum(result[:a]) + sum(loop) * b + sum(loop[:c])
print(ans)


(N, X, M) = map(int, input().split())
ans = 0
flag = [0] * (10 ** 5 + 2)
lst = [X]
for i in range(N):
	X = X ** 2 % M
	if flag[X] == 1:
		break
	flag[X] = 1
	lst.append(X)
preindex = lst.index(X)
preloop = lst[:preindex]
loop = lst[preindex:]
loopnum = (N - len(preloop)) // len(loop)
loopafternum = (N - len(preloop)) % len(loop)
ans = sum(preloop) + sum(loop) * loopnum + sum(loop[:loopafternum])
print(ans)


(N, X, M) = map(int, input().split())
(ans, tmp) = (X, X)
s = set()
s.add(X)
for i in range(1, N):
	tmp = tmp ** 2 % M
	if tmp == 0:
		break
	if tmp == 1:
		ans += N - i
		break
	if tmp not in s:
		s.add(tmp)
		ans += tmp
	else:
		s = list(s)
		idx = s.index(tmp)
		ans += sum(s[idx:]) * ((N - i) // (len(s) - idx))
		ans += sum(s[idx:idx + (N - i) % (len(s) - idx)])
		break
print(ans)


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) = map(int, input().split())
s = set([x])
t = [x]
p = 1
for i in range(n):
	x = x * x % m
	if x in s:
		break
	else:
		s.add(x)
		t.append(x)
	p += 1
if p == n:
	print(sum(s))
	exit()
q = t.index(x)
l = p - q
b = sum(t[q:p])
ans = sum(t[:q])
n -= q
ans += n // l * b + sum(t[q:q + n % l])
print(ans)


(N, X, M) = map(int, input().split())
Q = 0
for i in range(min(100, N)):
	Q += X
	X = X * X % M
N -= min(N, 100)
S = set([X])
P = X
A = X
R = 0
for i in range(M):
	A = A * A % M
	if A in S:
		R = i + 1
		break
	S.add(A)
	P += A
P *= N // R
N %= R
for i in range(N):
	P += X
	X = X * X % M
print(P + Q)


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) = list(map(int, input().split()))
D = [X]
E = set([X])
F = [0, X]
for i in range(M + 1):
	X = X ** 2
	X %= M
	if X in E:
		break
	D.append(X)
	E.add(X)
	F.append(F[-1] + X)
if N <= len(D):
	print(F[N])
else:
	for i in range(len(D)):
		if D[i] == X:
			break
	num = (N - i - 1) // (len(D) - i)
	res = (N - i - 1) % (len(D) - i)
	print(F[res + i + 1] + num * (F[-1] - F[i]))


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)


(N, X, M) = map(int, input().split())
existence = [0] * M
a = []
A = X
for i in range(N):
	if existence[A] != 0:
		break
	existence[A] = 1
	a.append(A)
	A = A * A % M
for i in range(len(a)):
	if a[i] == A:
		break
j = i
result = sum(a[:j])
a = a[j:]
N -= j
x = N // len(a)
y = N % len(a)
result += sum(a) * x + sum(a[:y])
print(result)


(n, x, m) = map(int, input().split())
s = x
t = {x}
u = [x]
for i in range(1, n):
	x = pow(x, 2, m)
	if x == 0:
		break
	if x == 1:
		s += n - i
		break
	if x in t:
		j = u.index(x)
		s = sum(u[:j])
		u = u[j:]
		s += (n - j) // len(u) * sum(u)
		s += sum(u[:(n - j) % len(u)])
		break
	s += x
	t |= {x}
	u += (x,)
print(s)


(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)


(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)


(n, x, m) = map(int, input().split())
ai = x
i = 0
memo = []
d = {}
tmp = 0
while True:
	if ai in d:
		break
	d[ai] = i
	memo.append(ai)
	ai = ai ** 2 % m
	i += 1
s = d[ai]
e = i
su = sum(memo[s:])
if n <= e + 1:
	print(sum(memo[0:n]))
else:
	zan = n - s
	ans = sum(memo[:s]) + zan // (e - s) * su
	if zan % (e - s):
		ans += sum(memo[s:s + zan % (e - s)])
	print(ans)


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


(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())
c1 = [X]
c2 = {X}
ans = X
for i in range(N - 1):
	X = pow(X, 2, M)
	if X not in c2:
		c1.append(X)
		c2.add(X)
		ans += X
	else:
		b = c1.index(X)
		break
else:
	print(ans)
	exit()
l = len(c1) - b
t = N - i - 1
ans += t // l * sum(c1[b:]) + sum(c1[b:b + t % l])
print(ans)


(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)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, x, m) = map(int, readline().split())
nxt = [x * x % m for x in range(m)]
wa = list(range(m))
ans = 0
while n:
	if n & 1:
		ans += wa[x]
		x = nxt[x]
	wa = [wa[nxt[i]] + wa[i] for i in range(m)]
	nxt = [nxt[i] for i in nxt]
	n >>= 1
print(ans)


(n, x, m) = map(int, input().split())
ans = 0
l = [x]
s = [0] * m
s[0] = 1
for i in range(n):
	x = x * x % m
	if s[x] == 1:
		break
	s[x] = 1
	l.append(x)
if x == 0:
	print(sum(l))
else:
	p = l[0]
	k = 1
	Su = 0
	while p != x and k < len(l):
		Su += p
		p = l[k]
		k += 1
	l = l[k - 1:]
	Su2 = 0
	for r in range((n - k) % len(l) + 1):
		Su2 += l[r]
	print(Su + (n - k) // len(l) * sum(l) + Su2)


(N, X, M) = map(int, input().split())
S = {X: 1}
path = [X]
cnt = 1
ans = X
a = X
for i in range(2, N + 1):
	a = a * a % M
	if a in S:
		cnt = i - S[a]
		break
	S[a] = i
	ans += a
	path.append(a)
pre_len = S[a] - 1
(Q, R) = divmod(N - pre_len - 1, len(path) - pre_len)
pre = sum(path[:pre_len])
cycle = sum(path) - pre
ans = a
for _ in range(R):
	a = a * a % M
	ans += a
print(pre + Q * cycle + ans)


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

def cal(x):
	return pow(x, 2, M)
memo = set()
lis = []
while X not in memo:
	memo.add(X)
	lis.append(X)
	X = cal(X)
pos = lis.index(X)
if pos >= N:
	print(sum(lis[:N]))
else:
	print(sum(lis[:pos]) + (N - pos) // (len(memo) - pos) * sum(lis[pos:]) + sum(lis[pos:(N - pos) % (len(memo) - pos) + pos]))


(N, X, M) = map(int, input().split())
existence = [False] * M
a = []
A = X
for i in range(N):
	if existence[A]:
		break
	existence[A] = True
	a.append(A)
	A = A * A % M
for i in range(len(a)):
	if a[i] == A:
		break
loop_start = i
result = sum(a[:loop_start])
a = a[loop_start:]
N -= loop_start
loops = N // len(a)
remainder = N % len(a)
result += sum(a) * loops + sum(a[:remainder])
print(result)


(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)


(N, X, M) = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
	li.append(X)
	isused[X] = True
	X = X ** 2 % M
	N -= 1
if N == 0:
	print(sum(li))
elif N != 0 and X in li:
	l = len(li)
	s = li.index(X)
	T = l - s
	q = (NN - s) // T
	r = (NN - s) % T
	print(sum(li) + sum((li[i] for i in range(s, len(li)))) * (q - 1) + sum((li[i] for i in range(s, s + r))))


(N, X, M) = map(int, input().split())
d = {}
x = X
A = []
init = 0
loop = 0
S = [0]
while x not in d:
	d[x] = 1
	A.append(x)
	S.append(S[-1] + A[-1])
	x = x * x % M
init = A.index(x)
loop = len(A) - init
if N <= init + loop:
	print(S[N])
else:
	l = (N - init) // loop
	r = (N - init) % loop
	print((S[-1] - S[init]) * l + S[init + r])


(n, x, m) = map(int, input().split())
set_ = set()
l = []
cnt = 0
dic = {}
while x not in set_ and cnt < n:
	set_.add(x)
	l.append(x)
	dic[x] = cnt
	cnt += 1
	x = x ** 2 % m
	if x == 0:
		l.append(0)
		break
if l[-1] == 0:
	print(sum(l))
	exit()
if cnt == n:
	print(sum(l))
	exit()
ans = sum(l[:dic[x]])
l = l[dic[x]:]
L = l + l
cnt = len(l)
n -= dic[x]
s = sum(l)
ans += n // cnt * s + sum(l[:n % cnt])
print(ans)


(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)


(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)])


(n, x, m) = map(int, input().split())
v = list(range(m))
p = [-1 for _ in range(m)]
a = x
p[a - 1] = 0
s = [x]
(l, r) = (n, n)
for i in range(n):
	a = a ** 2 % m
	if p[a - 1] >= 0:
		(l, r) = (p[a - 1], i + 1)
		break
	else:
		s.append(a)
		p[a - 1] = i + 1
ans = sum(s[:l])
if l != r:
	b = (n - 1 - i) // (r - l) + 1
	c = (n - 1 - i) % (r - l)
	ans += b * sum(s[l:r]) + sum(s[l:l + c])
print(ans)


(N, X, M) = list(map(int, input().split()))
s = {X}
l = [X]
i = 0
while True:
	a = l[-1] ** 2 % M
	if a in s:
		i = l.index(a)
		break
	else:
		s.add(a)
		l.append(a)
loop_length = len(l) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(l[:i]) + loop_cnt * sum(l[i:]) + sum(l[i:i + loop_res])
print(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())
A = [X]
x = X ** 2 % M
while x not in A:
	A.append(x)
	x = x ** 2 % M
if len(A) >= N:
	answer = sum(A[:N])
else:
	index = 0
	while A[index] != x:
		index += 1
	len_loop = len(A) - index
	num_loop = (N - index) // len_loop
	num_last = N - index - len_loop * num_loop
	answer = sum(A[:index]) + num_loop * sum(A[index:]) + sum(A[index:index + num_last])
print(answer)


import sys
from collections import deque, Counter, defaultdict
import bisect
import heapq
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
circle = nums.index(x)
if n < circle:
	print(sum(nums[:circle]))
else:
	times = (n - circle) // (cnt - circle)
	last = (n - circle) % (cnt - circle)
	print(sum(nums[:circle]) + sum(nums[circle:]) * times + sum(nums[circle:circle + last]))


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])


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


(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))


(n, x, m) = map(int, input().split())
l = [0 for i in range(m)]
ans = 0
y = []
i = 1
flag = 0
ys = n
while i < n + 1:
	if flag == 0:
		ans += x
	l[x] += 1
	x = x * x % m
	i += 1
	if l[x] == 2 and flag == 0:
		flag = 1
		ys = i
	if flag:
		if l[x] == 3:
			break
		y.append(x)
if len(y):
	(p, pp) = divmod(n - ys, len(y))
	print(ans + p * sum(y) + sum(y[:pp + 1]))
else:
	print(ans)


(N, X, M) = map(int, input().split())
checklist = [True] * 100000
ind = 0
l = [X]
while True:
	t = l[-1] ** 2 % M
	if checklist[t]:
		l.append(t)
		checklist[t] = False
	else:
		ind = l.index(t)
		break
S = sum(l[ind:])
L = len(l)
ans = 0
if N <= L:
	ans = sum(l[:N])
else:
	ans = sum(l)
	N -= L
	ans += S * (N // (L - ind))
	ans += sum(l[ind:ind + N % (L - ind)])
print(ans)


(n, x, m) = map(int, input().split())
id = [-1 for i in range(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 n <= d:
	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(ans)


(N, X, M) = list(map(int, input().split()))
A = X
sum_A = A
A_list = [X]
for i in range(1, N):
	A = A ** 2 % M
	if A in A_list:
		start = A_list.index(A)
		loop = A_list[start:]
		sum_A += sum(loop) * ((N - i) // len(loop)) + sum(loop[:(N - i) % len(loop)])
		break
	else:
		A_list.append(A)
	sum_A += A
	if A == 0:
		break
print(sum_A)


(N, X, M) = list(map(int, input().split()))
L = [0] * M
S = [0] * (M + 1)
cnt = 1
L[X] = 1
S[1] = X
t = X
cnt = 1
for i in range(N):
	t = t * t % M
	if L[t] != 0:
		r = L[t]
		break
	L[t] = i + 2
	S[cnt + 1] = S[cnt] + t
	cnt += 1
if N <= cnt:
	print(S[N])
	exit()
roop = cnt - r + 1
(d, m) = divmod(N - r + 1, roop)
ans = (S[cnt] - S[r - 1]) * d
ans += S[r + m - 1]
print(ans)


(N, X, M) = map(int, input().split())
id = [-1] * M
lis = []
tot = 0
le = 0
while id[X] == -1:
	id[X] = le
	le += 1
	lis.append(X)
	tot += X
	X = X ** 2 % M
c = le - id[X]
sm = 0
for i in range(id[X], le):
	sm += lis[i]
if N <= le:
	ans = 0
	for i in range(N):
		ans += lis[i]
	print(ans)
	exit()
ans = tot
N -= le
ans += N // c * sm
N %= c
for i in range(id[X], id[X] + N):
	ans += lis[i]
print(ans)


(N, X, M) = [int(_) for _ in input().split()]

def f(x, m):
	return x % m
P = [-1 for _ in range(M + 1)]
A = [X]
for i in range(N - 1):
	v = f(A[-1] ** 2, M)
	A.append(v)
	if P[v] != -1:
		break
	P[v] = i
v = f(A[-1] ** 2, M)
idx = P[v]
S = sum(A[idx + 1:])
(q, r) = divmod(N - len(A), len(A) - idx - 1)
ans = sum(A) + q * S + sum(A[idx + 1:idx + 1 + r])
print(ans)


(N, X, M) = map(int, input().split())
isUsed = [False] * M
isUsed[X] = True
S = [X]
st = X
while True:
	nx = X ** 2 % M
	if isUsed[nx]:
		st = nx
		break
	isUsed[nx] = True
	S.append(nx)
	X = nx
idx = S.index(st)
(L, R) = (S[:idx], S[idx:])
ans = sum(L[:N])
N = max(0, N - len(L))
(q, r) = divmod(N, len(R))
ans += q * sum(R) + sum(R[:r])
print(ans)


(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)


(n, x, m) = map(int, input().split())
set_a = set()
a = []
while len(a) < n:
	if x in a:
		break
	set_a.add(x)
	a.append(x)
	x = x ** 2 % m
ans = sum(a[:min(n, len(a))])
n -= len(a)
if n < 1:
	print(ans)
	exit()
i = a.index(x)
l = len(a) - i
ans += sum(a[i:]) * (n // l)
n %= l
ans += sum(a[i:i + n])
print(ans)


from collections import defaultdict
(N, X, M) = map(int, input().split())
ans = 0
d = defaultdict(lambda : -1)
x = X % M
for n in range(M + 100):
	if x in d:
		T = n - d[x]
		break
	else:
		d[x] = n
	x *= x
	x %= M
p = 0
y = x
for m in range(d[x], n):
	p += y
	y *= y
	y %= M
ans = 0
n = N
z = X % M
while n:
	ans += z
	n -= 1
	z *= z
	z %= M
	if z == x:
		ans += n // T * p
		n %= T
print(ans)


(n, x, m) = map(int, input().split())
ans = [x]
for _ in range(m):
	ans.append(pow(ans[-1], 2, m))
loop = [ans[-1]]
check = ans[-1]
for _ in range(m):
	next = pow(loop[-1], 2, m)
	if next == check:
		break
	else:
		loop.append(next)
if n <= m + 1:
	A = sum(ans[:n])
else:
	times = (n - m) // len(loop)
	amari = (n - m) % len(loop)
	A = sum(ans[:-1]) + sum(loop) * times + sum(loop[:amari])
print(A)


(n, x, m) = map(int, input().split())
li = [x]
se = {x}
for i in range(n - 1):
	x = x * x % m
	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)


(n, x, m) = map(int, input().split())
s = set()
ct = x
ans = [x]
s.add(x)
f = 0
for i in range(n - 1):
	ct **= 2
	ct %= m
	if ct not in s:
		s.add(ct)
		ans.append(ct)
	else:
		f = 1
		break
if f == 0:
	print(sum(ans))
	exit()
y = ans.index(ct)
z = sum(ans[y:len(ans)])
z2 = 0
for i in range((n - y) % (len(ans) - y)):
	z2 += ans[y + i]
print(sum(ans[0:y]) + z * ((n - y) // (len(ans) - y)) + z2)


(N, X, M) = map(int, input().split())
D = {i: 0 for i in range(M)}
L = [X]
c = X
D[X] = 0
S = X
for i in range(1, N):
	c = c ** 2 % M
	if D[c] == 0:
		D[c] = i
		L.append(c)
		S += c
		continue
	else:
		(p, q) = (D[c], i)
		break
else:
	print(S)
	exit()
cycle = L[p:q]
cycle_sum = sum(cycle)
cycle_num = (N - q) // (q - p)
rest = (N - q) % (q - p)
S += cycle_sum * cycle_num
S += sum(cycle[:rest])
print(S)


(n, x, m) = (int(x) for x in input().split())
A = [x]
used = {x}
while True:
	x = pow(x, 2, m)
	if x in used:
		index = A.index(x)
		break
	else:
		A.append(x)
		used.add(x)
if n <= len(A):
	print(sum(A[:n]))
else:
	ans = sum(A)
	n -= len(A)
	m = len(A) - index
	ans += n // m * sum(A[index:])
	ans += sum(A[index:index + n % m])
	print(ans)


(n, x, m) = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1:
	X[x] = len(P)
	P.append(sum_p)
	sum_p += x
	x = x * x % m
P.append(sum_p)
p_len = len(P) - 1
if n <= p_len:
	print(P[n])
	exit()
(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)


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
	ata = [0] + at[: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())
a = [x]
found = {x}
while True:
	y = a[-1] ** 2 % m
	a.append(y)
	if y in found:
		break
	found.add(y)
if n <= len(a):
	print(sum(a[:n]))
else:
	z = a.index(a[-1])
	a.pop()
	n -= z
	res = sum(a[:z])
	res += sum(a[z:]) * (n // (len(a) - z))
	res += sum(a[z:z + n % (len(a) - z)])
	print(res)


def f(x, m):
	return x ** 2 % m
(N, X, M) = map(int, input().split())
A = [X]
S = {X}
while True:
	X = f(X, M)
	if X in S:
		break
	else:
		A.append(X)
		S.add(X)
start = A.index(X)
l = len(A) - start
ans = sum(A[:start])
N -= start
ans += sum(A[start:]) * (N // l)
N %= l
ans += sum(A[start:start + N])
print(ans)


(N, X, M) = list(map(int, input().split()))
r = [-1 for _ in range(M)]
a = X
r[a] = 0
p = [a]
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) = 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)


(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)


(N, X, M) = map(int, input().split())
p = [0] * (M + 2)
sum = [0] * (M + 2)
p[X] = 1
sum[1] = X
f = 0
for i in range(2, N + 1):
	X = X ** 2 % M
	if p[X] != 0:
		j = p[X]
		f = i
		break
	else:
		sum[i] = X + sum[i - 1]
		p[X] += i
if f == 0:
	print(sum[N])
else:
	(d, mod) = divmod(N - j + 1, i - j)
	print(d * (sum[i - 1] - sum[j - 1]) + sum[j + mod - 1])


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 = 998244353
(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)


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) = 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)


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


(N, X, M) = map(int, input().split())
d = {}
l = []
for i in range(N):
	if X in d:
		break
	d[X] = i
	l.append(X)
	X = X * X % M
else:
	print(sum(l))
	exit()
s = d[X]
(q, r) = divmod(N - s, i - s)
ans = sum(l[:s]) + q * sum(l[s:i]) + sum(l[s:s + r])
print(ans)


(N, X, M) = map(int, input().split())
nxt = X
lst = []
dic = {}
for i in range(M + 1):
	if nxt in dic:
		loop_st = dic[nxt]
		loop_ed = i - 1
		break
	lst.append(nxt)
	dic[nxt] = i
	nxt = nxt ** 2 % M
v = N - loop_st
(q, r) = divmod(v, loop_ed - loop_st + 1)
pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])
print(pre_sum + loop_sum + post_sum)


(N, X, M) = map(int, input().split())
visited = [-1] * (M + 1)
x = X
i = 0
while visited[x] == -1:
	visited[x] = i
	x = x * x % M
	i += 1
loop_l = i - visited[x]
loop_s = x
ret = 0
x = X
while x != loop_s:
	ret += x
	x = x * x % M
	N -= 1
	if N == 0:
		break
if N > 0:
	i = 0
	while i != loop_l:
		ret += x * ((N - i + loop_l - 1) // loop_l)
		x = x * x % M
		i += 1
print(ret)


(n, x, m) = map(int, input().split())
a = x
r = [True for _ in range(m)]
s = []
while r[a]:
	r[a] = False
	s.append(a)
	a = pow(a, 2, m)
ai = s.index(a)
c = (n - len(s)) // (len(s) - ai)
d = n - len(s) - (len(s) - ai) * c
ans = sum(s) + sum(s[ai:]) * c + sum(s[ai:ai + d])
print(ans)


(n, x, m) = map(int, input().split())
a = set()
b = [x]
for i in range(m):
	x = pow(x, 2, m)
	if x in a:
		break
	a.add(x)
	b += [x]
j = b.index(x)
n -= j
c = b[j:]
ans = sum(b[:j]) + sum(c) * (n // len(c)) + sum(c[:n % len(c)])
print(ans)


(n, x, m) = map(int, input().split())
p = [x]
A = set([x])
f = 0
for i in range(n - 1):
	p.append(p[-1] ** 2 % m)
	if p[-1] in A:
		f = 1
		break
	else:
		A.add(p[-1])
if f == 0:
	print(sum(p))
else:
	for i in range(len(p)):
		if p[i] == p[-1]:
			loop = len(p) - i - 1
			break
	SUM = sum(p[i:-1])
	ans = sum(p) - p[-1]
	n -= len(p) - 1
	ans += SUM * (n // loop) + sum(p[i:i + n % loop])
	print(ans)


(n, x, m) = map(int, input().split())
A = []
al = [-1] * (m + 1)
cnt = 0
for i in range(n):
	if al[x % m] >= 0:
		break
	al[x % m] = cnt
	A.append(x)
	cnt += 1
	x = x ** 2 % m
if n <= al[x]:
	print(sum(A[:al[x]]))
	exit()
lena = len(A)
loop = A[al[x]:]
lenl = cnt - al[x]
n -= al[x]
cnt = n // lenl
print(sum(A[:al[x]]) + sum(loop) * cnt + sum(loop[:n % lenl]))


(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)


(n, x, m) = map(int, input().split())
dic = {}
a = x
s = 0
c = m
for i in range(1, n + 1):
	if a not in dic:
		s += a
		dic[a] = [i]
	elif len(dic[a]) == 1:
		s += a * (1 + (n - i) // (i - dic[a][0]))
		dic[a].append(i)
	else:
		break
	a = pow(a, 2, m)
print(s)


(n, x, m) = map(int, input().split())
A = [[0] * 2 for i in range(m)]
A[x] = [1, x]
a = x
f = -1
for i in range(10 ** 5 + 100):
	if i == n - 1:
		f = 0
		break
	x = x ** 2 % m
	a = a + x
	if A[x][0] != 0:
		f = 1
		break
	A[x] = [i + 2, a]
if f == 0:
	print(a)
elif f == 1:
	ans = A[x][1] + (a - A[x][1]) * ((n - A[x][0]) // (i + 2 - A[x][0]))
	for i in range((n - A[x][0]) % (i + 2 - A[x][0])):
		x = x ** 2 % m
		ans = ans + x
	print(ans)


(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)


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)


(N, X, M) = map(int, input().split())
l = [X]
p = [-1] * (M + 1)
p[X] = 0
x = 0
for i in range(N - 1):
	x = l[-1] ** 2 % M
	if p[x] >= 0:
		break
	l.append(x)
	p[x] = i + 1
x = p[x]
y = len(l) - x
print(sum(l[:x]) + (N - x) // y * sum(l[x:]) + sum(l[x:x + (N - x) % y]))


(n, x, m) = map(int, input().split())
r = []
s = set()
ans = x
a = x
for i in range(n - 1):
	b = a * a % m
	if b in s:
		j = r.index(b)
		N = n - 1 - i
		T = i - j
		S = sum(r[j:])
		ans += N // T * S
		N %= T
		ans += sum(r[j:j + N])
		break
	else:
		ans += b
		s.add(b)
		r.append(b)
		a = b
print(ans)


(n, x, m) = map(int, input().split())
s = set()
l = [x]
while x ** 2 % m not in s:
	v = x ** 2 % m
	s.add(v)
	l.append(v)
	x = v
idx = l.index(x ** 2 % m)
loop = len(l) - idx
if n < len(l):
	print(sum(l[:n]))
elif (n - idx) % loop == 0:
	print(sum(l[:idx]) + (n - idx) // loop * sum(l[idx:]))
else:
	print(sum(l[:idx]) + (n - idx) // loop * sum(l[idx:]) + sum(l[idx:idx + (n - idx) % loop]))


(N, X, M) = map(int, input().split())
T = []
K = [0] * M
p = X
for i in range(N):
	if K[p] == 1:
		break
	else:
		T.append(p)
	K[p] = 1
	p *= p
	p %= M
for i in range(N):
	if T[i] == p:
		break
ans = 0
ans += sum(T)
if N > len(T):
	L = sum(T[i:])
	q = len(T[i:])
	ans += L * ((N - len(T)) // q)
	ans += sum(T[i:i + (N - len(T)) % q])
print(ans)


(N, X, M) = map(int, input().split())
D = [-1] * M
A = [X]
for i in range(M):
	if D[X] >= 0:
		break
	D[X] = i
	X = X * X % M
	A.append(X)
st = D[X]
loop = A[st:-1]
if N <= st:
	ans = sum(A[:N])
else:
	Nl = N - st
	ans = sum(A[:st]) + sum(loop) * (Nl // len(loop)) + sum(loop[:Nl % len(loop)])
print(ans)


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


(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))


(N, X, M) = map(int, input().split())
exist = [0 for _ in range(M)]

def f(a, m):
	return a % m
S = 0
A = X
ls = []
for n in range(1, N + 1):
	if exist[A] == 0:
		exist[A] = n
		ls.append(A)
	else:
		term = n - exist[A]
		loop = ls[-term:]
		res = N - n + 1
		S += res // term * sum(loop) + sum(loop[:res % term])
		break
	S += A
	A = f(A ** 2, M)
print(S)


(n, x, m) = map(int, input().split())
li = [x]
a = x
q = 0
flag = False
for i in range(m):
	k = a ** 2 % m
	if k == 0:
		p = i + 1
		flag = True
		break
	if k in li:
		p = i + 1
		q = li.index(k)
		break
	li.append(k)
	a = k
K = sum(li)
li2 = li[q:]
K2 = sum(li2)
if not flag:
	ans = K + (n - p) // (p - q) * K2 + sum(li2[:(n - p) % (p - q)])
else:
	ans = sum(li[:n])
print(ans)


(N, X, M) = map(int, input().split())
tmp = X
seq = []
ans = 0
for i in range(N):
	if X in seq:
		break
	seq.append(X)
	X = X ** 2 % M
ans = sum(seq[:min(N, len(seq))])
N -= len(seq)
if N < 1:
	print(ans)
	exit()
i = seq.index(X)
l = len(seq) - i
ans += sum(seq[i:]) * (N // l)
N %= l
ans += sum(seq[i:i + N])
print(ans)


(N, X, M) = map(int, input().split())
ans = 0
sumlist = [X]
checklist = [-1] * (M + 1)
A = X

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
	if checklist[A - 1] != -1:
		ans = calcans(checklist[A - 1], i - 1, sumlist)
		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())
A = [X]
S = set()
for i in range(3 * 10 ** 6):
	nx = A[-1] ** 2 % M
	if nx in S:
		break
	S.add(nx)
	A.append(nx)
L = []
R = []
for (i, a) in enumerate(A):
	if a != nx:
		L.append(a)
	else:
		R = A[i:]
		break
ans = sum(L)
N -= len(L)
RS = sum(R)
ans += RS * (N // len(R))
if R:
	for i in range(N % len(R)):
		ans += R[i]
print(ans)


(n, x, m) = map(int, input().split())
l = [x]
c = 1
d = -1
f = 0
while x > 0 and c < n:
	g = x * x % m
	d = g
	if g in l:
		f = 1
		break
	l.append(g)
	x = g
	c += 1
s = sum(l)
if f == 1:
	r = l.index(g)
	o = (n - c) // (c - r)
	t = (n - c) % (c - r)
	s += o * sum(l[r:]) + sum(l[r:r + t])
print(s)


(n, x, m) = map(int, input().split())
li = [x]
seen = [False] * m
seen[x] = True
for i in range(n - 1):
	x = x * x % m
	if seen[x]:
		idx = li.index(x)
		break
	seen[x] = True
	li.append(x)
else:
	print(sum(li))
	exit(0)
ans = sum(li) + sum(li[idx:]) * ((n - len(li)) // (len(li) - idx)) + sum(li[idx:idx + (n - len(li)) % (len(li) - idx)])
print(ans)


(N, X, M) = map(int, input().split())
a = X * X % M
lis = [X]
while a not in lis:
	lis.append(a)
	a = a * a % M
i = lis.index(a)
lis1 = lis[:i]
lis2 = lis[i:]
ans = 0
if N <= len(lis1):
	ans = sum(lis1[:N])
else:
	ans = sum(lis1)
	n = N - len(lis1)
	ans += n // len(lis2) * sum(lis2)
	ans += sum(lis2[:n % len(lis2)])
print(ans)


(n, x, m) = map(int, input().split())
idx = [-1] * m
a = []
leng = 0
tot = 0
while idx[x] == -1:
	a.append(x)
	idx[x] = leng
	leng += 1
	tot += x
	x = x * x % m
c = leng - idx[x]
s = 0
for i in range(idx[x], leng):
	s += a[i]
ans = 0
if n <= leng:
	for i in range(n):
		ans += a[i]
else:
	ans += tot
	n -= leng
	ans += s * (n // c)
	n %= c
	for i in range(n):
		ans += a[idx[x] + i]
print(ans)


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


(n, x, m) = map(int, input().split())
A = [0, x]
d = {x: 1}
for i in range(2, n + 1):
	A.append(A[i - 1] ** 2 % m)
	if A[i] in d:
		j = d[A[i]]
		(q, r) = divmod(n - j + 1, i - j)
		print(sum(A[:j]) + q * sum(A[j:i]) + sum(A[j:j + r]))
		break
	else:
		d[A[i]] = i
else:
	print(sum(A))


(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) = map(int, input().split())
d = {X: 0}
l = [X]
s = X
for i in range(1, N):
	l += [l[i - 1] ** 2 % M]
	s += l[i]
	if l[i] in d:
		dl = l[d[l[i]] + 1:]
		s += sum(dl) * ((N - i - 1) // len(dl))
		if (N - i - 1) % len(dl) != 0:
			s += sum(dl[0:(N - i - 1) % len(dl)])
		break
	d[l[i]] = i
print(s)


(N, X, M) = map(int, input().split())
l = [X]
a = X
k = 0
for i in range(M):
	if a ** 2 % M not in l:
		l.append(a ** 2 % M)
		a = a ** 2 % M
	else:
		k = l.index(a ** 2 % M)
		break
sum = 0
for i in range(k, len(l)):
	sum += l[i]
ans = 0
ans += (N - k) // (len(l) - k) * sum
for i in range(min(k, N)):
	ans += l[i]
for i in range(1, (N - k) % (len(l) - k) + 1):
	ans += l[k + i - 1]
print(ans)


import sys
(n, x, m) = map(int, input().split())
a = [0] * (m + 2)
cnt = [0] * (m + 2)
(a[1], f) = (x, x)
cnt[f] = 1
if x == 0:
	print(0)
	sys.exit()
for i in range(2, m + 1):
	f = f * f % m
	a[i] = f
	if cnt[f] == 0:
		cnt[f] = 1
	else:
		break
ind = a[1:].index(f) + 1
ans = sum(a[:ind]) + sum(a[ind:i]) * ((n - ind + 1) // (i - ind))
p = (n - ind + 1) % (i - ind)
ans += sum(a[ind:ind + p])
print(ans)


(N, X, M) = map(int, input().split())
a = X
S = [0, a]
lasts = [None] * 10 ** 5
for i in range(1, N):
	a = a * a % M
	if a == 0:
		break
	if lasts[a] is not None:
		LA = lasts[a]
		T = i - LA
		print(S[-1] + (S[-1] - S[-T - 1]) * ((N - i) // T) + S[-T - 1 + (N - i) % T] - S[-T - 1])
		exit()
	S.append(S[-1] + a)
	lasts[a] = i
print(S[-1])


from collections import deque
(N, X, M) = map(int, input().split())
D = deque([X], M)
R = {X: 0}
x = X
for _ in range(min(N - 1, M + 1)):
	x = x ** 2 % M
	if x in R:
		l = R[x]
		m = len(D) - l
		(q, r) = divmod(N - l, m)
		print(sum((D[i] for i in range(l))) + (q + 1) * sum((D[i] for i in range(l, l + r))) + q * sum((D[i] for i in range(l + r, l + m))))
		break
	else:
		R[x] = len(D)
		D.append(x)
else:
	print(sum(D))


(n, x, m) = map(int, input().split())
s = set()
idx = {i: -1 for i in range(m)}
cumsum = [0]
val = x
idx[val] = 0
for i in range(n):
	cumsum.append(cumsum[-1] + val)
	val = pow(val, 2, m)
	if idx[val] != -1:
		break
	idx[val] = i + 1
if len(cumsum) > n:
	print(cumsum[n])
else:
	loop_len = i + 1 - idx[val]
	print((cumsum[i + 1] - cumsum[idx[val]]) * ((n - idx[val]) // loop_len) + cumsum[idx[val] + (n - idx[val]) % loop_len])


(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]))