Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,ma,mb = inm()
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp = [[BIG]*(100*n+1) for i in range(100*n+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(100*n+1) for i in range(100*n+1)]
    for i in range(10*t+1):
        for j in range(10*t+1):
            if dp[i][j]<BIG:
                dp2[i][j] = min(dp2[i][j],dp[i][j])
                dp2[i+a[t]][j+b[t]] = min( \
                     dp2[i+a[t]][j+b[t]], dp[i][j]+c[t])
    dp = dp2
mn = BIG
for i in range(1,5000):
    if i*max(ma,mb)>n*100:
        break
    #ddprint(f"i {i} n {n} ma {ma} mb {mb} ima {i*ma}")
    mn = min(mn, dp[i*ma][i*mb])
print(-1 if mn==BIG else mn)


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,ma,mb = inm()
a = []
b = []
c = []
for i in range(n):
    aa,bb,cc = inm()
    a.append(aa)
    b.append(bb)
    c.append(cc)
dp = [[BIG]*(10+1) for i in range(10+1)]
dp[0][0] = 0
for t in range(n):
    dp2 = [[BIG]*(10*(t+1)+1) for i in range(10*(t+1)+1)]
    for i in range(10*t+1):
        for j in range(10*t+1):
            if dp[i][j]<BIG:
                dp2[i][j] = min(dp2[i][j],dp[i][j])
                dp2[i+a[t]][j+b[t]] = min( \
                     dp2[i+a[t]][j+b[t]], dp[i][j]+c[t])
    dp = dp2
mn = BIG
for i in range(1,5000):
    if i*max(ma,mb)>n*10:
        break
    #ddprint(f"i {i} n {n} ma {ma} mb {mb} ima {i*ma}")
    mn = min(mn, dp[i*ma][i*mb])
print(-1 if mn==BIG else mn)
### BUGGY CODE ###

def main():
	n, k = map(int, input().split())
	costs = list(map(int, input().split()))
	before = [0 for i in range(k)]
	for step in range(1, n):
		nex_vals = []
		for j in range(1,k+1):
			if j <= step: nex_vals.append(abs(costs[step] - costs[step-j]) + before[k-j])
		nex_val = min(nex_vals)
		before = before[1:] + [nex_val]
	return before[-1]
print(main())


### FIXED CODE ###

def main():
	n, k = map(int, input().split())
	costs = list(map(int, input().split()))
	v= [0] * n
	for step in range(1, n):
		v[step] = min([v[j] + abs(costs[step]-costs[j]) for j in range(max(0,step-k), step)])
	return v[-1]
print(main())
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans *= ((2*i) - (count*2))
    count += 1
  if S[2*i + 1] == "B":
    ans *= ((2*i + 1) - (count*2))
    count += 1

if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)

### FIXED CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans = ans * ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans = ans * ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)
### BUGGY CODE ###

n = list(map(int,input().split()))
a = list(map(int,input().split()))

for i in range(n[1]):
    a[a.index(max(a))] = int(max(a) / 2)

print(sum(a))

### FIXED CODE ###

import heapq

n = list(map(int,input().split()))
a = list(map(int,input().split()))

#heapqでは最小値しか取り出せないので，*(-1)することで最大値を取り出す
for i in range(len(a)):
    a[i] *= -1

#リストを優先度付きキューにする
heapq.heapify(a)

for i in range(n[1]):
    #最小値(実際には最大値であるはずの値)を取り出す
    tmp = heapq.heappop(a)

    #取り出した値を2で割って切り下げで優先度付きキューに挿入
    heapq.heappush(a, int(tmp/2))

print(-sum(a))

'''
max()はO(N)．heapqはO(logN)
これだと発想はあっているが，O(NM)となるので間に合わない
for i in range(n[1]):
    a[a.index(max(a))] = int(max(a) / 2)

print(sum(a))
'''
### BUGGY CODE ###

N, M = map(int, input().split())
AB = []
for i in range(N) :
    AB.append(list(map(int, input().split())))

AB = sorted(AB, key=lambda x:(x[0],x[1]))

ans = 0
#print(AB)
for i in range(1, M + 1) :
    maxIncome = 0
    anker = -1
    for j in range(len(AB)) :
        #print(AB[j][0])
        if AB[j][0] <= i :
            if AB[j][1] > maxIncome :
                maxIncome = AB[j][1]
                anker = j
                #print('A', j, maxIncome)
                continue
        else :
            break
    ans += maxIncome
    if len(AB) == 0 :
        break
    if anker != -1:
        AB.pop(anker)

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

for i in range(N) :
    A, B = map(int, input().split())
    if A <= M :
        AB[A-1].append(B)

#print(AB)
queue = []
ans = 0
for i in range(M) :
    for j in range(len(AB[i])) :
        heappush(queue, -AB[i][j])

    if len(queue) != 0 :
        ans += -heappop(queue)

print(ans)


'''
ans = 0
#print(AB)
for i in range(1, M + 1) :
    maxIncome = 0
    anker = -1
    for k in ABkeys :
        #print(AB[j][0])
        if k <= i :
            if heappop(AB[k]) > maxIncome :
                maxIncome = AB[j][0]
                anker = k
                #print('A', j, maxIncome)
                continue
        else :
            break
    ans += maxIncome
    if len(AB) == 0 :
        break
    if anker != -1:
        AB[anker].pop(0)
        if len(AB[anker]) == 0 :
            AB.remove


print(ans)
'''
'''
N, M = map(int, input().split())
AB = []
for i in range(N) :
    AB.append(list(map(int, input().split())))

AB = sorted(AB, key=lambda x:(x[0],x[1]))

ans = 0
#print(AB)
for i in range(1, M + 1) :
    maxIncome = 0
    anker = -1
    for j in range(len(AB)) :
        #print(AB[j][0])
        if AB[j][0] <= i :
            if AB[j][1] > maxIncome :
                maxIncome = AB[j][1]
                anker = j
                #print('A', j, maxIncome)
                continue
        else :
            break
    ans += maxIncome
    if len(AB) == 0 :
        break
    if anker != -1:
        AB.pop(anker)

print(ans)
'''
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
N=int(input())
X=list(map(int,input().split()))
lastX=X.pop()
mod=10**9+7
ferumaC=10**5+1
fac=[1,1]
for i in range(2,ferumaC):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]
ipow=[pow(i,mod-2,mod) for i in range(ferumaC)]
count=0


for i in range(1,len(X)):
    count2=0
    for n in range(min(i,len(X)-i)):

        a=((len(X)-1)//i)*i+n
        if a>len(X)-1:
            a-=i

        #print(n,a,i)
        count2+=X[a]-X[n]


    count=(count+ipow[i+1]*ipow[i]*count2)%mod
for i in range(len(X)):
    count=(count+(lastX-X[i])*ipow[len(X)-i])%mod
count=count*fac[N-1]%mod
print(count)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
N=int(input())
X=list(map(int,input().split()))
lastX=X.pop()
mod=10**9+7
ferumaC=10**5+1
fac=[1,1]
for i in range(2,ferumaC):
    fac.append(fac[i-1]*i%mod)
ipow=[pow(i,mod-2,mod) for i in range(ferumaC+1)]

ruiipow=[0,ipow[2]*ipow[1]%mod]

for i in range(2,ferumaC):
    ruiipow.append((ruiipow[i-1]+ipow[i+1]*ipow[i])%mod)

count=0
"""for i in range(1,len(X)):
    count2=0
    for n in range(min(i,len(X)-i)):
        a=((len(X)-1)//i)*i+n
        if a>len(X)-1:
            a-=i
        #print(n,a,i)
        count2+=X[a]-X[n]
    count=(count+ipow[i+1]*ipow[i]*count2)%mod"""
for i in range(len(X)):

    count=(count+(ruiipow[i]-ruiipow[len(X)-i-1])*X[i])%mod
    #print(i,count*fac[N-1]%mod)

for i in range(len(X)):
    count=(count+(lastX-X[i])*ipow[len(X)-i])%mod
count=count*fac[N-1]%mod
print(count)
### BUGGY CODE ###

N = int(input())
A = input().split()
for i in range(len(A)):
    A[i] = int(A[i])

answer = A[0]
overl = False

for i in range(N-1):
    answer *= A[i+1]

if answer > 10**18:
    print("-1")
else:
    print(answer)

### FIXED CODE ###

N = int(input())
org = input().split()
for i in range(len(org)):
    org[i] = int(org[i])
A = sorted(org)

answer = A[0]
overl = False

for i in range(N-1):
    answer *= A[i+1]
    if answer > 10**18:
        overl = True
        break

if overl:
    print("-1")
else:
    print(answer)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline


def main():
  S = input()[:-1]
  Q = int(input())

  reverse = False
  for i in range(Q):
    line = input().split()
    if line[0] == '1':
      reverse = not(reverse)
    else:
      if reverse ^ (int(line[1])-1):
        S = S + line[2]
      else:
        S = line[2] + S

  print(''.join(reversed(S)) if reverse else S)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

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


def main():
  S = input()[:-1]
  Q = int(input())

  q = deque([S])
  reverse = False
  for i in range(Q):
    line = input().split()
    if line[0] == '1':
      reverse = not(reverse)
    else:
      if reverse ^ (int(line[1])-1):
        # S = S + line[2]
        q.append(line[2])
      else:
        # S = line[2] + S
        q.appendleft(line[2])

  print(''.join(list(reversed(''.join(q)))) if reverse else ''.join(q))


if(__name__ == '__main__'):
  main()
### BUGGY CODE ###

s = int(input())

x1, y1, x2, y2, x3, y3 = 0, 0, 0, 0, 0, 0

while True:
    if s >= 10e9:
        for i in range(int(s**0.5), 0, -1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i - y1
                break
    else:
        for i in range(1, int(s**0.5) + 1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i - y1
                break

    if x2 == 0 and y3 == 0:
        x1 += 1
        y1 += 1
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

from math import factorial
n = int(input())
a_list = sorted(list(map(int, input().split())))

a_i_index = len(a_list) - 1
a_i = a_list[-1]
max = 0
max_j_index = None

nobori = True

tmp = a_list[0]
koeta = None
for j_index in range(n):
    if a_list[j_index] * 2 > a_i:
        koeta = j_index
        break
    else:
        tmp = j_index

comb = factorial(a_i) / (factorial(a_i - a_list[koeta]) * factorial(a_list[koeta]))
comb2 = 0
if koeta != 0:
    comb2 = factorial(a_i) / (factorial(a_i - a_list[koeta-1]) * factorial(a_list[koeta-1]))


if comb > comb2:
    print(*[a_i,a_list[koeta]])
else:
    print(*[a_i, a_list[koeta-1]])



### FIXED CODE ###

n = int(input())
a_list = sorted(list(map(int, input().split())))
 
a_i_index = len(a_list) - 1
a_i = a_list[-1]
max = 0
max_j_index = None
 
nobori = True
 
tmp = a_list[0]
koeta = None
for j_index in range(n):
    if a_list[j_index] * 2 > a_i:
        koeta = j_index
        break
    else:
        tmp = j_index
 
comb2 = 0
if n == 2:
    print(*[a_list[1], a_list[0]])
elif koeta == 0:
    print(*[a_i, a_list[koeta]])
elif (a_list[koeta]- a_i/2) > (a_i/2 - a_list[koeta-1]):
    print(*[a_i,a_list[koeta-1]])
else:
    print(*[a_i, a_list[koeta]])
### BUGGY CODE ###

import sys
from collections import Counter

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    d = Counter(A)

    for i in range(M):
        b, c = map(int, input().split())
        for cand in [k for k in sorted(d.keys()) if k < c]:
            if b == 0:
                continue
            if d[cand] < b:
                d[c] += d[cand]
                b -= d[cand]
                d[cand] = 0
            else:
                d[cand] -= b
                d[c] += b
                b = 0

    ans = 0
    for k, v in d.items():
        if v == 0:
            continue
        ans += k * v

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N, M = map(int, input().split())
    A = []
    for i in list(map(int, input().split())):
        A.append((i, 1))
    for i in range(M):
        b, c = map(int, input().split())
        A.append((c, b))

    A = sorted(A)
    # print(A)
    cnt = 1
    ans = 0
    while cnt <= N:
        b, c = A.pop()
        ans += b
        if c > 1:
            c -= 1
            A.append((b, c))
        cnt += 1
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
dic = {i: [] for i in range(1, N + 1)} 
XY_list = [None] * M
for i in range(M):
  X, Y = map(int, input().split())
  dic[X].append(Y)
  XY_list[i] = (X, Y)
for j in range(1, N + 1):
  dic[j].sort()
for x in XY_list:
  print(str(x[0]).zfill(6)+str(dic[x[0]].index(x[1]) + 1).zfill(6))

### FIXED CODE ###

N, M = map(int, input().split())
XY_list = [[] for i in range(N)]
ans_list = [None] * M
for i in range(M):
  X, Y = map(int, input().split())
  XY_list[X - 1].append((Y, i))
for j, k in enumerate(XY_list):
  k.sort()
  for l, (y, m) in enumerate(k):
    ans_list[m] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
print(*ans_list, sep = "\n")
### BUGGY CODE ###

from heapq import heappush, heappop
import numpy as np
 
num_q = int(input())
x = 0
f = 0
low = []
high = []
odd = False
num_a = 0
 
for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    if odd:
      if n >= -low[0]:
        heappush(high, n)
      else:
        heappush(low, -n)
        heappush(high, -heappop(low))
    else:
      if num_a and n > -low[0]:
        heappush(high, n)
        heappush(low, -heappop(high))
      else:
        heappush(low, -n)

    x_tmp = -low[0]
    if odd:
      f += m + np.abs(x - n)
    else:
      f += m + np.abs(x_tmp - n)

    odd = ~odd
    x = x_tmp
    num_a += 1

### FIXED CODE ###

from heapq import heappush, heappop

num_q = int(input())
x = 0
f = 0
low = []
high = []
odd = False
num_a = 0
 
for _ in range(num_q):
  q = input()
  if q[0] == '2':
    print(x, f)
  else:
    _, n, m = map(int, q.split(" "))
    if odd:
      if n >= -low[0]:
        f += m + n + low[0]
        heappush(high, n)
      else:
        f += m - n - low[0]
        heappush(low, -n)
        heappush(high, -heappop(low))
    else:
      f += m
      if num_a == 0:
        heappush(low, -n)
      else:
        if n > -low[0]:
          if n > high[0]:
            f += n - high[0]
          heappush(high, n)
          heappush(low, -heappop(high))
        else:
          f += - n - low[0]
          heappush(low, -n)

    odd = ~odd
    x = -low[0]
    num_a += 1
### BUGGY CODE ###

n = int(input())
values = input().split()

mult = 1
for i in range(len(values)):
  mult *= int(values[i])
  
if mult > 10**18:
  print(-1)
else:
  print(mult)


### FIXED CODE ###

def main():
  n = int(input())
  values = list(map(int, input().split()))
  if 0 in values:
    print(0)
    return

  mult = 1
  for i in values:
    mult *= i
    if mult > 1000000000000000000:
      print(-1)
      return
  print(mult)

main()
### BUGGY CODE ###

inputEnzan=input().split()

def keisan(inputEnzan):
    while True:
        stockFornumber=[]
        index=0
        length=len(inputEnzan)
        if length==1:
            break
        while index<length:
            if inputEnzan[index]=="+" or inputEnzan[index]=="-" or inputEnzan[index]=="*":
                if len(stockFornumber)==2:
                    if inputEnzan[index]=="+":
                        inputEnzan[index]=stockFornumber[0]+stockFornumber[1]
                        stockFornumber=[]
                        inputEnzan[index-1]="null"
                        inputEnzan[index-2]="null"

                    elif inputEnzan[index]=="-":
                        inputEnzan[index]=stockFornumber[0]-stockFornumber[1]
                        stockFornumber=[]
                        inputEnzan[index-1]="null"
                        inputEnzan[index-2]="null"

                    else:
                        inputEnzan[index]=stockFornumber[0]*stockFornumber[1]
                        stockFornumber=[]
                        inputEnzan[index-1]="null"
                        inputEnzan[index-2]="null"
                else:
                    pass

            else:
                stockFornumber.append(int(inputEnzan[index]))
            index+=1

        while "null" in inputEnzan:
            inputEnzan.remove("null")

    print(inputEnzan[0])

keisan(inputEnzan)     



### FIXED CODE ###

class stack:
    def __init__(self):
        self.s = []
    def push(self, x):
        self.s.append(x)
    def pop(self):
        ret = self.s[-1]
        del self.s[-1]
        return ret
    def size(self):
        return len(self.s)

inputL = input().split()
s = stack()
for char in inputL:
    if char == '+':
        b = s.pop()
        a = s.pop()
        s.push(a+b)
    elif char == '-':
        b = s.pop()
        a = s.pop()
        s.push(a-b)
    elif char == '*':
        b = s.pop()
        a = s.pop()
        s.push(a*b)
    elif char == '/':
        b = s.pop()
        a = s.pop()
        s.push(a/b)
    else:
        s.push(int(char))
print(s.pop())
### BUGGY CODE ###

s = input()
s_num = int(s)
len_s = len(s)
count = 0
for i in range(1,len_s):
    for j in range(len_s-i+1):
        if int(s[j:i+j])%2019==0:
            count+=1
print(count)

        

### FIXED CODE ###

s=list(input())
s.reverse()
s_len = len(s)

list = [0 for _ in range(2019)]
ans = 0
mod = 2019
li = [0]
digit = 0
for i in range(s_len):
    li.append((li[i] + int(s[i])*pow(10,digit,mod))%mod)
    digit+=1
for i in range(s_len+1):
    list[li[i]]+=1
for i in range(2019):
    x = list[i]
    ans += x*(x-1)/2
print(int(ans))
### BUGGY CODE ###

N, W = map(int, input().split())
kpsk_list = [list(map(int, input().split())) for _ in range(N)]
#print(kpsk_list)
dp = [[0]*(W+1) for _ in range(N+1)]
#print(dp)
for n in range(1, N+1): #何個目までのアイテムを考慮するか
  for w in range(W+1): #各重さでの価値の最大値を求める.
    #print(f"n:{n},w:{w}")
    if w - kpsk_list[n-1][0] < 0: 
      dp[n][w] = dp[n-1][w]
    else:
      dp[n][w] = max(dp[n-1][w], dp[n-1][w - kpsk_list[n-1][0]] + kpsk_list[n-1][1])
    #print(dp)

print(dp[N][W])
  # dp[n]について各重さsum_w(=0~W)の時の最大価値をdpテーブルに保存していく.


### FIXED CODE ###

N, W = map(int, input().split())
kpsk_list = [list(map(int, input().split())) for _ in range(N)]
#print(kpsk_list)
dp = [[0]*(W+1) for _ in range(N+1)]
#print(dp)
for n in range(1, N+1): #何個目までのアイテムを考慮するか
  for w in range(W+1): #各重さでの価値の最大値を求める.
    #print(f"n:{n},w:{w}")
    if w - kpsk_list[n-1][0] < 0: 
      dp[n][w] = dp[n-1][w]
    else:
      dp[n][w] = max(dp[n-1][w], dp[n-1][w - kpsk_list[n-1][0]] + kpsk_list[n-1][1])
    #print(dp)

print(dp[N][W])
#dp[n]について各重さsum_w(=0~W)の時の最大価値をdpテーブルに保存していく.
### BUGGY CODE ###

#d
n=int(input())
x=list(input())

def popcount(m):
    return bin(m).count("1")

popcount0 = popcount(int( "0b"+"".join(x) ,0 ))

for i in range(n):
    xx = x[:]
    if xx[i]=="0":
        xx[i] = "1"
        pop = popcount0+1
    else:
        xx[i] = "0"
        pop = popcount0-1
        
    intxi = int( "0b"+"".join(xx) ,0 )
#    print(intxi,intxi%pop)
    if intxi==0:
        print(0)
        continue
    else:
        c=0
        while intxi!=0:
            c+=1
            intxi=intxi%popcount(intxi)
            #print(m)
        print(c)
#        print("f(n)=",c)

### FIXED CODE ###

#d 
n=int(input())
x=input()

def popcount(m):
    return bin(m).count("1")

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    

jisho = ["yet"]*n
# pow2ip = .5
# pow2im = .5

for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:
        pow2im = pow(2,n-i-1,popcount0-1)

    if False:
        pass
    
    
    else:
        intxi=1
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    pop = popcount0+1
                    intxi = (intx_mod_pp1 + pow2ip%pop )%pop
                else:
                    pop = popcount0-1
                    intxi = (intx_mod_pm1 - pow2im%pop )%pop        
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
    
#        print("f(n)=",c)
### BUGGY CODE ###

n,x,m=map(int,input().split())
ans=x
a=[x]
if n==1:
  print(ans)
else:
  for i in range(2,n+1):
    tmp=a[-1]**2%m
    if tmp not in a:
      a.append(tmp)
      ans+=tmp
    else:
      t=a.index(tmp)
      if len(a)-t>=n-i+1:
        ans+=sum(a[t:t+n-i+1])
        break
      else:
        t=a.index(tmp)
        tmp_a=(n-i+1)//(len(a)-t)
        tmp_b=(n-i+1)-(len(a)-t)*tmp_a
        ans+=sum(a[t:])*tmp_a+sum(a[t:t+tmp_b])
        break
  print(ans)

### FIXED CODE ###

n,x,m=map(int,input().split())
ans=x
a=[x]
d={}
d[x]=1
if n==1:
  print(ans)
else:
  for i in range(2,n+1):
    tmp=a[-1]**2%m
    if d.get(tmp,0)==0:
      a.append(tmp)
      d[tmp]=1
      ans+=tmp
    else:
      t=a.index(tmp)
      if len(a)-t>=n-i+1:
        ans+=sum(a[t:t+n-i+1])
        break
      else:
        t=a.index(tmp)
        tmp_a=(n-i+1)//(len(a)-t)
        tmp_b=(n-i+1)-(len(a)-t)*tmp_a
        ans+=sum(a[t:])*tmp_a+sum(a[t:t+tmp_b])
        break
  print(ans)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0,0)
sum = 0
for i in range(1, N):
    for j in range(i + 1, N + 1):
        sum += (A_list[i] * A_list[j])
        sum = sum % 1000000007
print(sum)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
A_list.insert(0, 0)

cum_sum = 0
cum_sum_list = []
for i in range(N + 1):
    cum_sum += A_list[i]
    cum_sum_list.append(cum_sum)

ans = 0
for i in range(1, N+1):
    ans += A_list[i] * (cum_sum_list[N] - cum_sum_list[i])
    ans = ans % 1000000007
print(ans)