Solve in Python:
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.
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)