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

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

dp = [0] * (N+1)
dp[1] = 1
dp[2] = -1

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)



### FIXED CODE ###

import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

mod = 998244353

N, K = rl()
lr = []
for i in range(K):
	l, r = rl()
	lr.append((l,r))
lr.sort()

dp = [0] * (N+1)
dp[1] = 1
dp[2] = -1

ans = 0
s = 0
flags = [1] * K
for i in range(1, N+1):
	s += dp[i]
	s %= mod
	for k in range(K):
		if flags[k] == 0:
			break
		l, r = lr[k]
		if i+l <= N:
			dp[i+l] += s
			if i+r+1 <= N:
				dp[i+r+1] -= s
			else:
				ans += s
				ans %= mod
				break
		else:
			flags[k] = 0
			break
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

ans = N-1
for i in range(N):
    cnt = 0
    for j in range(i):
        if S[j] == "W":
            cnt += 1
    for k in range(i+1, N):
        if S[k] == "E":
            cnt += 1
    ans = min(ans, cnt)

print(ans)

### FIXED CODE ###

N = int(input())
S = input()

cnt = S[1:].count("E")
ans = cnt
for i in range(1, N):
    if S[i-1] == "W":
        cnt += 1
    if S[i] == "E":
        cnt -= 1
    ans = min(ans, cnt)

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

N = int(input())
minmum = 10**5
def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)

for i in range(1, N):
    for j in range(1, N):
        if i + j == N:
            min_sum = digitSum(i) + digitSum(j)
            if min_sum < minmum:
                minmum = min_sum

print(minmum)

### FIXED CODE ###

N = int(input())
minmum = 10**5
def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)

for i in range(1, N):
    j = N - i
    min_sum = digitSum(i) + digitSum(j)
    if min_sum < minmum:
        minmum = min_sum

print(minmum)
### BUGGY CODE ###

s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()
#print(t)
if (s[0]=="?"):
    for i in range(10):
        dp[0][t[0]*i%13] = +1
else:
    dp[0][t[0]*int(s[0])%13] += 1
for i in range(1,len(s)):
    if (s[i]=="?"):
        for j in range(13):
            for k in range(10):
                dp[i][(j + t[i]*k)%13] += dp[i-1][j]
                dp[i][(j + t[i]*k)%13] %= mod
    else:
        for j in range(13):
            #print(i,j,(j + t[i]*int(s[i]))%13)
            dp[i][(j + t[i]*int(s[i]))%13] += dp[i-1][j]
            dp[i][(j + t[i]*int(s[i]))%13] %= mod             
#print(dp)
print(dp[len(s)-1][5])

### FIXED CODE ###

s = input()
mod = 10**9+7
dp = [[0]*13 for _ in range(len(s))]
t = [1]
for i in range(len(s)-1):
    t.append(t[-1]*10%13)
t.reverse()
#print(t)
if (s[0]=="?"):
    for i in range(10):
        dp[0][t[0]*i%13] = +1
else:
    dp[0][t[0]*int(s[0])%13] += 1
for i in range(1,len(s)):
    if (s[i]=="?"):
        for j in range(13):
            for k in range(10):
                dp[i][(j + t[i]*k)%13] += dp[i-1][j]
                dp[i][(j + t[i]*k)%13] %= mod
    else:
        for j in range(13):
            #print(i,j,(j + t[i]*int(s[i]))%13)
            dp[i][(j + t[i]*int(s[i]))%13] += dp[i-1][j]
            dp[i][(j + t[i]*int(s[i]))%13] %= mod             
#print(dp)
print(dp[len(s)-1][5])
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = sr()
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return
    lp = [0]*P
    for i in range(N):
        lp[int(S[i:])%P] += 1
    ans = lp[0]
    for i in range(P):
        ans += max(lp[i]*(lp[i]-1)//2, 0)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

N, K = map(int,input().split(' '))
S = input()
S2=[]
key=S[0]
tmpcnt=1
if key=='0':
    S2.append(0)
for i in range(1,len(S)):
    if key!=S[i]:
        if key == '0':
            S2.append(-1*tmpcnt)
        else:
            S2.append(tmpcnt)
        key=S[i]
        tmpcnt=1
    else:
        tmpcnt+=1
if key == '0':
    S2.append(-1*tmpcnt)
    S2.append(0)
    S2.append(0)
else:
    S2.append(tmpcnt)
    S2.append(0)
    S2.append(0)
#print(S2)
max=0
for i in range(0,len(S2),2):
    tmp=S2[i]
    maxj=len(S2)-1
    for j in range(1,K*2+1):
        tmp+=abs(S2[min(i+j,maxj)])
        #print(S2[i],S2[min(i+j,maxj)])
    if tmp >= max:
        max=tmp
    #print(tmp)
print(max)

### FIXED CODE ###

N, K = map(int,input().split(' '))
S = input()
S2=[]
key=S[0]
tmpcnt=1
if key=='0':
    S2.append(0)
S2.append(0)
S2.append(0)
for i in range(1,len(S)):
    if key!=S[i]:
        if key == '0':
            S2.append(-1*tmpcnt)
        else:
            S2.append(tmpcnt)
        key=S[i]
        tmpcnt=1
    else:
        tmpcnt+=1
if key == '0':
    S2.append(-1*tmpcnt)
    S2.append(0)
    S2.append(0)
else:
    S2.append(tmpcnt)
    S2.append(0)
    S2.append(0)
#print(S2)
max=0
tmp=S2[0]
maxj=len(S2)-1
for j in range(1,K*2+1):
    tmp+=abs(S2[min(0+j,maxj)])
    #print(S2[i],S2[min(i+j,maxj)])
if tmp >= max:
    max=tmp
    #print(tmp)

for i in range(2,len(S2),2):
    tmp-=abs(S2[i-1])
    tmp-=abs(S2[i-2])
    tmp+=abs(S2[min(i+j-1,maxj)])
    tmp+=abs(S2[min(i+j,maxj)])
    #print(i-1,i-2,i+j-1,i+j)
    #print(tmp)
    if tmp>= max:
        max=tmp
print(max)
### BUGGY CODE ###

mod = 1000000007
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
        for j in  range(i+1, n):
                ans  += ((a[i] %mod) * (a[j] % mod)) % mod
                ans = ans % mod
print(ans)

### FIXED CODE ###

d = 1000000007
n = int(input())
a = list(map(int, input().split()))
summation = sum(a)
diagonal = 0
for i in range(len(a)):
        diagonal += a[i] ** 2 
ans = (((summation  ** 2) - diagonal) // 2) % d
print(ans)
### BUGGY CODE ###

def bubble_sort(A, N):
    flag = True
    c = 0
    i = 0
    while flag:
        for j in range(N-1, i, -1):
            flag = False
            if A[j] < A[j-1]:
                A[j],  A[j-1] = A[j-1], A[j]
                c += 1
                flag = True
        i += 1

    print " ".join(map(str, A))
    print c


N = int(raw_input())
A = map(int, raw_input().split())

bubble_sort(A, N)

### FIXED CODE ###

def bubble_sort(A, N):
    flag = True
    i, c = 0, 0
    while flag:
        flag = False
        for j in range(1, N-i):
              if A[j] < A[j-1]:
                  A[j],  A[j-1] = A[j-1], A[j]
                  flag = True
                  c += 1
        i += 1
    
    print " ".join(map(str, A))
    print c


N = int(raw_input())
A = map(int, raw_input().split())
 
bubble_sort(A, N)
### BUGGY CODE ###

n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i
#print(ListPos2)
ListPos = [-1, -1] + [ListPos2[n]] + [n, n]
for i in reversed(range(1, n)):
	tempPos = ListPos2[i]
	while (True):
		tempPos += 1
		if (tempPos in ListPos):
			ListPos.insert(ListPos.index(tempPos), ListPos2[i])
			break
	pos = ListPos.index(ListPos2[i])
	low1 = ListPos[pos] - ListPos[pos-1]
	low2 = ListPos[pos-1] - ListPos[pos-2]
	high1 = ListPos[pos+1] - ListPos[pos]
	high2 = ListPos[pos+2] - ListPos[pos+1]
	points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

def q3():
    N = int(input())
    S = []
    for _ in range(N):
        S.append(''.join(sorted(list(input()))))

    def combinations_count(n, r):
        """ 組み合わせ総数を計算 """
        import math
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    ans = 0
    unique_list = set(S)
    for u in unique_list:
        cnt = S.count(u)
        if cnt >= 2:
            ans += combinations_count(cnt, 2)

    print(ans)

    
if __name__ == '__main__':
    q3()


### FIXED CODE ###

def q3():
    N = int(input())
    from collections import deque
    S = deque()
    for _ in range(N):
        S.append(''.join(sorted(list(input()))))

    ans = 0
    d = {}  # key:文字列 value:出現回数
    for s in S:
        if s in d:
            ans += d[s]
            d[s] += 1
        else:
            d[s] = 1

    print(ans)


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

import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in aa:
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))

### FIXED CODE ###

import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in set(aa):
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))
### BUGGY CODE ###

N,C = map(int,input().split())
D = []
for i in range(C):
    D.append(list(map(int,input().split())))
c = []
for i in range(N):
    c.append(list(map(int,input().split())))

current_minimum = 1000 * 500 * 500 + 1

import itertools
for (c0,c1,c2) in itertools.permutations(range(C), 3):
	color = [c0,c1,c2]
	tmp = 0
	for (i,j) in itertools.product(range(N),range(N)):
		current_color = c[i][j]
		target_color = color[((i+1)+(j+1)) % 3]
		tmp += D[current_color - 1][target_color-1]
	if current_minimum >= tmp:
		current_minimum = tmp
print(current_minimum)

### FIXED CODE ###

N,C = map(int,input().split())
D = []
for i in range(C):
    D.append(list(map(int,input().split())))
c = []
for i in range(N):
    c.append(list(map(int,input().split())))

import itertools
current_minimum = 1000 * 500 * 500 + 1
Z = []
Z.append([0]*C)
Z.append([0]*C)
Z.append([0]*C)
#print(Z)

for (i,j) in itertools.product(range(N),range(N)):
	cur_mod = ((i+1)+(j+1)) % 3
	cur_color = c[i][j]
	#print(cur_mod)
	#print(cur_color)
	Z[cur_mod][cur_color-1] += 1

current_minimum = 1000 * 500 * 500 + 1
for (c0,c1,c2) in itertools.permutations(range(C), 3):
	tmp = 0
	color = [c0,c1,c2]
	for cur_mod in range(3):
		target_color = color[cur_mod]
		for cur_color in range(C):
			tmp += Z[cur_mod][cur_color] * D[cur_color][target_color]
	if current_minimum >= tmp:
		current_minimum = tmp
print(current_minimum)
### BUGGY CODE ###

def cs(n, p, c):
    global count, m
    if p >= count:
        return m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
count = n
print(cs(n, 0, c))


### FIXED CODE ###

def cs(n, p, c):
    global count, m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return n
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
count = n
print(cs(n, 0, c))
### BUGGY CODE ###

n, k = map(int, input().split(' '))
s = input()
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)

sum_max= 0
for i in range(len(s10)//2+1):
  sum_i = sum(s10[2*i:2*i+2*k+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)

### FIXED CODE ###

n, k = map(int, input().split(' '))
s = input()
if k >= n:
  print(n)
  exit()
  
s10 = []
cnt = 0
s_prev = '1'
for si in s+'x':
  if si == s_prev:
    cnt += 1
  else:
    s10.append(cnt)
    cnt = 1
  s_prev = si
if s[-1] == '0':
  s10.append(0)
if len(s10) < 2*k + 1:
  print(n)
  exit()

sum_i = sum(s10[:2*k+1])
sum_max= sum_i

for i in range(len(s10)//2-k):
  sum_i += (s10[2*i + 2*k + 1] + s10[2*i + 2*k + 2] - s10[2*i] - s10[2*i+1])
  sum_max = max(sum_i, sum_max)
  
print(sum_max)
### BUGGY CODE ###

# D

N, M = list(map(int, input().split()))
# ABs = [list(map(int, input().split())) for i in range(M)]

adj_matrix = [[10**9] * N for i in range(N)]
for i in range(M):
    ab = list(map(int, input().split()))
    adj_matrix[ab[0]-1][ab[1]-1] = 1
    adj_matrix[ab[1]-1][ab[0]-1] = 1
 
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
import numpy as np
 
csr = csgraph_from_dense(adj_matrix, null_value=10**9)
from_starts, procs = dijkstra(csr, indices=[0], return_predecessors =True)
from_start = from_starts[0]
proc = procs[0]
 
if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(int(proc[i+1]) + 1)

### FIXED CODE ###

# D

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import breadth_first_order

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

row = []
col = []
for i in range(M):
    r, c = list(map(int, input().split()))
    row.append(c-1)
    col.append(r-1)

data = [1] * (M)

csr = csr_matrix((data, (row, col)), shape=(N, N))
_, proc = breadth_first_order(csr, 0, directed=False)

if -9999 in proc[1:]:
  print('No')
else:
  print('Yes')
  print('\n'.join((proc[1:]+1).astype('str')))
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [0] * (10**6+1)

    def make_divisors(n):  # nの約数を列挙
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort()
        return divisors

    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = 1
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x] == 1:
                flag = False
                break
        bl[a] = 1
        if flag:
            answer += 1

    print(answer)

main()

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)
### BUGGY CODE ###

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

parent=[i for i in range(M)]
depth=[0 for i in range(M)]

def root(x):
  while x!=parent[x]:
    x=parent[x]
  return parent[x]
  
def same(x,y):
  return root(x)==root(y)

def union(x,y):
  x=root(x)
  y=root(y)
  if x==y:
    return
  if depth[x]>depth[y]:
    parent[y]=x
  else:
    parent[x]=y
    if depth[x]==depth[y]:
      depth[x]+=1
      
h=[None]*N
langs=set()
for i in range(N):
  k,*h=map(int,input().split())
  for j in range(k-1):
    langs.add(h[j]-1)
    union(h[j]-1,h[j+1]-1)
  langs.add(h[k-1]-1)
  
roots=set()
for l in langs:
  roots.add(root(l))
  
print(("NO","YES")[len(roots)==1])

### FIXED CODE ###

# 人も言語もグラフの頂点と見なす
# ある人がある言語を話せる場合連結となる
# 頂点のキーは[言語 or 人][番号(人番号 or 言語番号)]
# 0:言語 1:人

N,M = map(int,input().split())
from collections import defaultdict
E = [[],[]]
E[0] = [[] for i in range(M)]
E[1] = [[] for i in range(N)]

for i in range(N):
  langs = list(map(int,input().split()))[1:]
  for lang in langs:
    E[1][i].append((0,lang-1))
    E[0][lang-1].append((1,i))
    
# 任意の頂点からBFSして、全ての人の頂点が往訪済みになればOK
from collections import deque
q = deque([])
# 人で、0番目からスタート
q.append((1,0))
seen = [[],[]]
seen[0] = [False for i in range(M)]
seen[1] = [False for i in range(N)]

while q:
  kind,v = q.popleft()
  if seen[kind][v]:
    continue
  seen[kind][v] = True
  children = E[kind][v]
  for child in children:
    q.append([child[0],child[1]])
    
for s in seen[1]:
  if not s:
    print("NO")
    break
else:
  print("YES")
### BUGGY CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))
B = copy.copy(A)

result = []

for i in range(N//2):
    if i < N -2:
        s_1 = A[2*i+1]
        s_2 = A[2*i]
        for j in range(2*i+2, N):
            s_1 = s_1 ^ A[j]
            s_2 = s_2 ^ A[j]
        result.append(str(s_1))
        result.append(str(s_2))
        for j in range(2*i+1, N):
            A[j] = int(result[-1])^int(result[-2])^A[j]
 
    else:
        result.append(str(A[N-1]))
        result.append(str(A[N-2]))
        break

print(' '.join(result)) 

### FIXED CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))

result = ['' for _ in range(N)]
s = A[0]
for i in range(1,N):
    s = s ^ A[i]

for i in range(N):
    result[i] = str(s ^ A[i])

print(' '.join(result))
### BUGGY CODE ###

N = int(input())
S = list(input())

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = list(input())

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

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

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
if ans>10**18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
a=sorted(a)
for i in a:
    ans*=i
    if i==0:
        print(0)
        exit()
    elif ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])



### FIXED CODE ###

H, N = map(int, input().split())
dp = [10 ** 18] * (H + 1)

dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)  # nj: 次のjのindex, 配列外参照しないようにminをとる
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])
### BUGGY CODE ###

def main():
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = list(map(int,input().split()))
  MOD = 10**9+7
  
  L = A[0]
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    ans += L//a
    ans %= MOD
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

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

N, K = map(int, input().split())
h = list(map(int, input().split())) + [float("inf")] * (K-1)

dp = [0] * N + [float("inf")] * K
for i in range(N-1)[::-1]:
    temp = float("inf")
    for k in range(1, K+1):
        temp = min(temp, abs(h[i+k] - h[i]) + dp[i+k])
    dp[i] = temp

print(dp[0])


### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split())) + [float("inf")] * (K-1)

dp = [0] * N + [float("inf")] * K
for i in range(N-1)[::-1]:
    temp = float("inf")
    for k in range(1, K+1):
        temp = min(temp, abs(h[i+k] - h[i]) + dp[i+k])
    dp[i] = temp

print(dp[0])
### BUGGY CODE ###

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

min_diff = float('inf')

for i in range(1, N):
  l_sum = sum(a[:i])
  r_sum = sum(a[i:])
  min_diff = min(min_diff, abs(l_sum - r_sum))

print(min_diff)


### FIXED CODE ###

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

min_diff = float('inf')
a_sum = sum(a)
l_sum = 0

for i in range(N - 1):
  l_sum += a[i]
  min_diff = min(min_diff, abs(l_sum * 2 - a_sum))

print(min_diff)
### BUGGY CODE ###

n=int(input())
alist=[int(input()) for i in range(n)]
for i in range(n):
    if i == 0:
        max_a = 0
    else:
        max_a = max(alist[0:i])
    if i == n-1:
        max_b = alist[-1]
    else:
        max_b = max(alist[i+1:])
    print(max([max_a, max_b]))

### FIXED CODE ###

n=int(input())
alist=[int(input()) for i in range(n)]
b=sorted(alist, reverse=True)
for a in alist:
    if a < b[0]:
        print(b[0])
    elif b[0] <= a:
        print(b[1])
### BUGGY CODE ###

import numpy as np

n = int(input())
max_n = int(n ** 0.5)
memo = np.zeros((max_n, max_n, max_n))


for x in range(1, max_n):
    for y in range(1, max_n):
        for z in range(1, max_n):
            memo[x][y][z] = x**2+y**2+z**2+x*y+y*z+z*x

for i in range(1, (n + 1)):
    print(np.count_nonzero(memo == i))


### FIXED CODE ###

import numpy as np

n = int(input())
max_n = int(n ** 0.5)
memo = np.zeros((max_n, max_n, max_n))

ans = [0]*(n+1)

for x in range(1, max_n):
    for y in range(1, max_n):
        for z in range(1, max_n):
            s = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if s < n+1:
                ans[s] += 1


for i in range(1, n+1):
    print(ans[i])
### BUGGY CODE ###

import numpy as np
X = int(input())
ans = 1
for b in range(int(np.ceil(np.sqrt(X)))):
    p = 0
    while b**p <= X:
        p += 1
    p -= 1
    ans = max(ans, b**p)
print(ans)


### FIXED CODE ###

import numpy as np
X = int(input())
ans = 1
for b in range(2, 1+int(np.ceil(np.sqrt(X)))):
    p = 0
    while np.power(b, p) <= X:
        p += 1
    p -= 1
    ans = max(ans, np.power(b, p))
print(ans)