Problem:
 Score : 500 points    Problem Statement Let us denote by f(x, m) the remainder of the Euclidean division of x by m .  Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M) .
Find \displaystyle{\sum_{i=1}^N A_i} .      Constraints  1 \leq N \leq 10^{10}  0 \leq X < M \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  X  M       Output Print \displaystyle{\sum_{i=1}^N A_i} .        Sample Input 1 6 2 1001      Sample Output 1 1369  The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369 .       Sample Input 2 1000 2 16      Sample Output 2 6  The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6 .       Sample Input 3 10000000000 10 99959      Sample Output 3 492443256176507

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

ans = 0
f = [-1]*m 
f[x] = 0

ansl = [x]
curr_x = x
loop_start = -1
for i in range(n-1):
    cnt = i+1
    x2 = (curr_x**2)%m
    if f[x2] == -1:
        ansl.append(x2)
        f[x2] = cnt
    else:
        loop_start = f[x2]
        break
    curr_x = x2
else:
    print(sum(ansl))
    exit()

amari = ansl[0:loop_start]

n_rem = n - loop_start
loop_l = ansl[loop_start:]
loop_len =len(loop_l)
loop_sum = sum(loop_l)

loop_cnt = n_rem//loop_len
loop_amari = n_rem - loop_cnt*loop_len

ans = sum(amari) + sum(loop_l)*loop_cnt + sum(loop_l[:loop_amari])
print(ans)

Solution (Python):
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]))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

N, X, M = map(int, input().split())
now = X
l = [X]
s = set()
s.add(X)

for i in range(N-1):
    now = now*now%M
    
    if now in s:
        for i in range(len(l)):
            if l[i]==now:
                mark = i
                break
        
        ans = sum(l[:mark])
        siz = len(l)-mark
        tot = sum(l[mark:])
        ans += (N-mark)//siz*tot
        ama = (N-mark)%siz
        
        for i in range(mark, mark+ama):
            ans += l[i]
        
        print(ans)
        exit()
    
    l.append(now)
    s.add(now)

print(sum(l))

Solution (Python):
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)

Solution (Python):
import sys
input = sys.stdin.readline

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

A = [0] * m
for i in range(m):
    A[i] = (i*i)%m

V = [-1] * m
B = [x]
xx = x

cnt = 0
while V[xx] == -1:
    V[xx] = cnt
    cnt += 1
    xx = A[xx]
    B.append(xx)

end = V[xx]





S = [B[0]]
for i in range(1, len(B)):
    S.append(B[i] + S[-1])




if end >= n:
    print(sum(B[:n]))
else:
    n -= end+1
    
    ans = sum(B[:end+1])
    
    ans += sum(B[end+1:]) * (n // (len(S)-end-1))
    
    ans += sum(B[end+1:end+1+n % (len(S)-end-1)])
    print(ans)

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

val = [-1] * (mod + 100)
val[X] = 1

a = X
idx = 2
memo = [X]

while True:
    a = a * a % mod
    if val[a] != -1:
        last = a
        break
    memo.append(a)
    val[a] = idx
    idx += 1




if N <= len(memo):
    print(sum(memo[:N]))
else:
    ans = sum(memo)
    N -= len(memo)
    i = memo.index(last)
    L = len(memo) - i

    sm = sum(memo[i:])
    d, m = divmod(N, L)
    ans += sm * d
    for x in range(i, i + m):
        ans += memo[x]
    print(ans)

Solution (Python):
def f(a, m):
    return a**2%m

def main():
    N, X, M = map( int, input().split())
    A = [X]
    T = [False]*M
    T[X] = True
    now = X
    while True:
        now = f(now, M)
        if T[now]:
            break
        T[now] = True
        A.append(now)
    R = len(A)
    for i in range(R-1,-1,-1):
        if now == A[i]:
            L = i
            break
    
    if N <= L:
        print( sum(A[:N]))
        return
    ans = sum(A[:L])
    loopsum = sum(A[L:])
    loopsize = R-L
    N -= L
    ans += N//loopsize*loopsum
    N -= N//loopsize*loopsize
    now = A[L]
    while N > 0:
        ans += now
        now = f(now,M)
        N -= 1
    print(ans)
if __name__ == '__main__':
    main()

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



set_ = set([x])
res = [x]
for i in range(m + 200):
    x = x ** 2 % m
    if x in set_:
        break
    res.append(x)
    set_.add(x)

if len(res) >= n:
    print(sum(res[0:n]))
    exit()

init = 0
init_terms = 0
ans = 0
for i in range(len(res)):
    if res[i] == x:
        l = i
        break
    init += res[i]
    init_terms += 1

ans = init
lap = res[l:]
sum_lap = sum(lap)
len_lap = len(lap)



div, mod = divmod(n - init_terms, len_lap)
ans += div * sum_lap + sum(lap[0:mod])
print(ans)

Solution (Python):
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)

Solution (Python):
def solve(n, x, m):
    result = [x]
    checked = [0] * m
    checked[x] = 1
    while len(result) < n:
        x = x * x % m
        if checked[x] > 0:
            break
        result.append(x)
        checked[x] = len(result)
    else:
        return sum(result)

    l = len(result)
    i = checked[x]
    before_len = i - 1
    loop_len = l - i + 1
    loop_sum = sum(result[before_len:])
    d, e = divmod(n - before_len, loop_len)
    ans = sum(result[:before_len]) + loop_sum * d + sum(result[before_len:before_len + e])
    return ans


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

print(solve(n, x, m))

Solution (Python):
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)

Solution (Python):
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)

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

L = [-1] * M

a = X
i = 0
while True:
    if L[a] != -1:
        B = L[a]
        C = i - L[a]
        break
    L[a] = i
    a = a * a % M
    i += 1


ans = 0
if N <= B + C:
    a = X
    for i in range(N):
        ans += a
        a = a * a % M
else:
    a = X
    for i in range(B):
        ans += a
        a = a * a % M
    temp = 0
    for i in range(B, B+C):
        temp += a
        a = a * a % M
    ans += (N-B) // C * temp
    for i in range((N-B)%C):
        ans += a
        a = a * a % M
print(ans)

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



mod_list = [x]
mod_dict = {x: 0}
now = x
idx = 0

while True:
    now = now ** 2
    now %= m

    idx += 1
    if now in mod_dict:
        
        period = idx - mod_dict[now]
        initial = mod_dict[now]
        break
    else:
        mod_list.append(now)
        mod_dict[now] = idx
    




if n <= initial:
    print(sum(mod_list[:n]))
else:
    ans = 0
    ans += sum(mod_list[:initial])

    loop_num = (n - initial) // period
    rest = (n - initial) % period

    ans += sum(mod_list[initial:]) * loop_num
    ans += sum(mod_list[initial: initial+rest])
    print(ans)

Solution (Python):
N, X, M = map(int, input().split())
loop = [X]
appeared = set(loop)
while True:
  n = loop[-1] ** 2 % M
  if n in appeared:
    break
  else:
    loop.append(n)
    appeared.add(n)
if N <= len(loop):
  print(sum(loop[:N]))
  exit()
  
i = loop.index(n)
preloop = loop[:i]
loop = loop[i:]

total = sum(preloop)
N -= len(preloop)

total += sum(loop) * (N // len(loop))
for l, _ in zip(loop, range(N % len(loop))):
  total += l
print(total)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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)

Solution (Python):
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]))

Solution (Python):
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)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8), cache=True)
def main(N, X, M):
    A = np.empty(M + 10, np.int64)
    A[0] = X
    first = np.full(M, -1, np.int64)
    n = 0
    while True:
        n += 1
        A[n] = A[n - 1] * A[n - 1] % M
        if first[A[n]] >= 0:
            period = n - first[A[n]]
            offset = first[A[n]] + 1
            break
        first[A[n]] = n
    if N <= offset:
        return A[:N].sum()
    x = A[:offset].sum()
    N -= offset
    q, r = divmod(N, period)
    x += q * A[offset:offset + period].sum()
    x += A[offset:offset + r].sum()
    return x

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

print(main(N, X, M))

Solution (Python):
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]))

Solution (Python):
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]))

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N,X,M=mint()
ans=X
se={X:1}
l=[0,X]
tmp=X
for k in range(2,N+1):
    tmp=(tmp*tmp)%M
    if tmp in se:
        i=se[tmp]
        ans=sum(l[:i])
        N-=(i-1)
        ans+=(N//(k-i))*sum(l[i:k])
        N-=(N//(k-i))*(k-i)
        for t in range(N):
            ans+=l[i+t]
        break
    se[tmp]=k
    l.append(tmp)
    ans+=tmp
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
mod_appeared = [False] * M
A_cycle = [X]
mod_appeared[X] = True
A = X * X % M
while not mod_appeared[A]:
    A_cycle.append(A)
    mod_appeared[A] = True
    A = A * A % M


if N < len(A_cycle):
    print(sum(A_cycle[:N]))
    exit()

cycle_start = A_cycle.index(A)
cycle_len = len(A_cycle) - cycle_start
cycle_sum = sum(A_cycle[cycle_start:])
prefix_sum = sum(A_cycle[:cycle_start])

q, r = divmod(N - cycle_start, cycle_len)
ans = prefix_sum + q * cycle_sum + sum(A_cycle[cycle_start:cycle_start + r])
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, x, mod = map(int, input().split())

    seen = [0] * mod
    ans = 0
    A = []
    ii = -1
    for i in range(N):
        if seen[x] == 0:
            seen[x] = 1
        elif seen[x] == 1:
            A.append(x)
            seen[x] = 2
        elif seen[x] == 2:
            ii = i
            break
        ans += x
        x = (x * x) % mod
    if ii == -1:
        print(ans)
    else:
        rem = N - ii
        ans += sum(A) * (rem // len(A))
        rem %= len(A)
        for j in range(rem):
            ans += A[j]
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,X,M = map(int,input().split())
R = [X]
dr = {}
for i in range(M):
    dr[i] = 0
m = min(N,M)
for i in range(m):
    r = R[-1]
    r = r**2%M
    if dr[r] == 1:
        break
    R.append(r)
    dr[r] = 1
for i in range(len(R)):
    if r == R[i]:
        break
a = 0
b = sum(R)
for j in range(i):
    a += R[j]
    b -= R[j]
n = len(R) - i
t = N - i
p = t // n
q = t % n
c = 0
for j in range(q):
    c += R[i+j]
ans = a + b*p + c
print(ans)

Solution (Python):
def main():
    N, X, M = [int(s) for s in input().split()]

    sums = [0]
    s = 0
    seen = {}
    for i in range(N):
        if X in seen:
            previ = seen[X]
            
            seq_length = i - previ
            remaining_full = (N - i) // seq_length
            remaining_part = (N - i) - remaining_full * seq_length
            s += (sums[-1] - sums[-seq_length-1]) * remaining_full
            s += sums[remaining_part-seq_length-1] - sums[-seq_length-1]
            print(s)
            return
        s += X
        sums.append(s)
        seen[X] = i

        X = X * X % M

    print(s)

main()

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

slow = x
fast = x
out = 0

while n:
    if n != nn and slow == fast:
        break
    out += slow
    n -= 1

    slow = (slow * slow) % m
    fast = (fast * fast) % m
    fast = (fast * fast) % m

head = slow
curr_sum = slow
curr_count = 1
slow = (slow * slow) % m
while slow != head:
    curr_count += 1
    curr_sum += slow
    slow = (slow * slow) % m

while n % curr_count:
    out += slow
    n -= 1
    slow = (slow * slow) % m

out += (n // curr_count) * curr_sum
print(out)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n, x, m = map(int, input().split())
    loop = [x]
    check = [False for _ in range(m + 1)]
    check[x] = True
    x2 = x
    for _ in range(n - 1):
        x2 = x2 ** 2 % m
        if check[x2]:
            break
        check[x2] = True
        loop.append(x2)
    else:
        print(sum(loop))
        return
    pos = loop.index(x2)
    ans = sum(loop[:pos])
    loop2 = loop[pos:]
    l = len(loop2)
    n -= pos
    ans += sum(loop2) * (n // l)
    ans += sum(loop2[:n % l])
    print(ans)
    
    
main()

Solution (Python):
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)

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, x, m = na()
hit = {}
hit[x] = 0
a = [x]

pe = -1
while True:
    v = a[-1] * a[-1] % m
    if v in hit:
       pe = len(a)-hit[v]
       break
    a.append(v)
    hit[v] = len(a)-1
ta = len(a) - pe
if n <= len(a):
    print(sum(a[0:n]))
else:
    cy = (n-ta) // pe
    u = (n-ta) % pe + ta
    print(sum(a[0:u]) + cy*sum(a[ta:]))

Solution (Python):
n,x,m = map(int, input().split())
ai = x
tmp = [ai]
used = set(tmp)
for i in range(n):
    nxt = ai**2 % m
    if nxt in tmp:
        break
    tmp.append(nxt)
    ai = nxt
if len(tmp) == n:
    ans = sum(tmp)
    print(ans)
    exit()

first = tmp.index(nxt)
ans = 0
l = []
for i in range(len(tmp)):
    if i < first:
        ans += tmp[i]
        n -= 1
    else:
        l.append(tmp[i])
m = len(l)
x,y = divmod(n, m)
ans += sum(l)*x
for i in range(y):
    ans += l[i]
print(ans)