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

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

import fractions
import copy
from functools import reduce

#最大公約数を求める関数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

l = []
temp_A = A
for i in range(N):
    temp_A = copy.deepcopy(A)
    del temp_A[i]
    l.append(gcd_list(temp_A))

print(max(l))

### FIXED CODE ###

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

import fractions
import copy
from functools import reduce

#最大公約数を求める関数
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

l = []
sorted_A = sorted(A)
ind = 0
for i in range(1, len(A)):
    if gcd_list([sorted_A[0], sorted_A[i]]) == 1:
        ind = i
        break
if ind == 0:
    ind = 1
for i in [0,ind]:
    sorted_A = sorted(A)
    del sorted_A[i]
    l.append(gcd_list(sorted_A))

print(max(l))
### BUGGY CODE ###

import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
import random
D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]
ld=[0]*(27)
for i in range(1,D+1):
    ma=0
    t=0
    for j in range(1,27):
        tmp=s[i][j]+(i-ld[j])*(D-i+1)*c[j]
        if tmp>ma:
            ma=tmp
            t=j
    T.append(t)
    ld[t]=i

sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score

ma=point()
TT=T[:]
for i in range(100000):
    T=[random.randrange(1,27) for i in range(D+1)]
    tmp=point()
    if tmp>ma:
        ma=tmp
        TT=T[:]

        

T=TT[:]
now=point()
for i in range(100000):
    d1,q1=random.randrange(1,D+1),random.randrange(1,27)
    d2,q2=random.randrange(1,D+1),random.randrange(1,27)
    old1=T[d1]
    old2=T[d2]
    T[d1]=q1
    T[d2]=q2
    new=point()
    if new>now:
        now=new
    else:
        T[d1]=old1
        T[d2]=old2

for i in T[1:]:
    print(i)

### FIXED CODE ###


import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")

D=N()
c=[0]+L()
s=[[0]*27]+[[0]+L() for i in range(D)]

dp=[]
T=[0]
for i in range(1,D+1):
    ma=0
    t=0
    for j in range(1,27):
        if s[i][j]>ma:
            ma=s[i][j]
            t=j
    T.append(t)
        
sc=sum(c)
def point():
    ld=[0]*(27)
    score=-sc*((D+1)*D//2)
    for i in range(1,D+1):
        t=T[i]
        score+=s[i][t]+(i-ld[t])*(D-i+1)*c[t]
        ld[t]=i
    return score


now=point()
import random
for i in range(1000):
    d,q=random.randrange(1,D+1),random.randrange(1,27)
    old=T[d]
    T[d]=q
    new=point()
    if new>now:
        now=new
    else:
        T[d]=old
for i in T[1:]:
    print(i)
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
*K, = map(int,input().split())

"""
nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()
"""

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)

### FIXED CODE ###

N = int(input())
S = input()
Q = int(input())
*K, = map(int,input().split())

nD = S.count("D")
nC = S.count("C")
if nD < nC:
    S = S[::-1].replace("D","c").replace("C","d").upper()

D = [0]*(N+1)
cntM = [0]*(N+1)
sumM = [0]*(N+1)
ans = [0]*Q
for i,s in enumerate(S):
    D[i+1] = D[i]
    cntM[i+1] = cntM[i]
    sumM[i+1] = sumM[i]
    if s=="D":
        D[i+1] += 1
    elif s=="M":
        cntM[i+1] += 1
        sumM[i+1] += D[i]
    elif s=="C":
        for j,k in enumerate(K):
            ik = max(0,i-k+1)
            d = D[ik]
            ans[j] += (sumM[i]-sumM[ik]) - d*(cntM[i]-cntM[ik])
for out in ans:
    print(out)
### BUGGY CODE ###

def bin_search1(L1,L2,l,N):#長すぎる辺の個数を返す
    low = 0
    high = N-1
    while high-low>1:
        mid = (low+high)//2
        if (L1+L2<=l[mid]):#長すぎ
            high = mid
        else:
            low = mid
    if L1+L2>l[high]:#全部ok
        return 0
    elif L1+L2<=l[low]:#全部ng
        return N
    else:
        return N-high

def bin_search2(L1,L2,l,N):#短すぎる辺の個数を返す
    low = 0
    high = N-1
    while high-low>1:
        mid = (low+high)//2
        if (abs(L1-L2)>=l[mid]):
            low = mid
        else:
            high = mid
    if abs(L1-L2)<l[low]:
        return 0
    elif abs(L1-L2)>=l[high]:
        return N
    else:
        return high

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(N):
    for j in range(N):
        if i!=j:
            L_temp = L#修正面倒なため
            a = L[i]
            b = L[j]
            if i<j:
                L_temp.pop(j)
                L_temp.pop(i)
                ans += (N-2-bin_search1(a,b,L_temp,N-2)-bin_search2(a,b,L_temp,N-2))
                L.insert(i,a)
                L.insert(j,b)
            else:
                L_temp.pop(i)
                L_temp.pop(j)
                ans += (N-2-bin_search1(a,b,L_temp,N-2)-bin_search2(a,b,L_temp,N-2))
                L.insert(j,b)
                L.insert(i,a)
                
ans = ans//6

print(ans)

### FIXED CODE ###

from bisect import bisect＿left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(N-1):
    for j in range(i+1,N):
        ans += bisect_left(L,L[i]+L[j])-(j+1)

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

n,m = map(int, input().split())
p = [0]*m 
for i in range(m):
    p[i] = input().split()

AC=[]
WA=0
for i in range(m):
    if p[i][1]=="AC" and p[i][0] not in AC:
        AC.append(p[i][0])
    elif p[i][1]=="WA" and p[i][0] not in AC and [p[i][0],"AC"] in p:
        WA=WA+1
print(len(AC),WA)

### FIXED CODE ###

n,m = map(int, input().split())
p = [0]*m 

for i in range(m):
    p[i] = input().split()
AC=[[0,-1] for j in range(n)]
k=0
WA=0
for i in range(m):
    if p[i][1]=="AC" and AC[int(p[i][0])-1][0]==0 :
        AC[int(p[i][0])-1][0]=1
        AC[int(p[i][0])-1][1]=i
        k=k+1
for i in range(m):
    if p[i][1]=="WA" and AC[int(p[i][0])-1][0]==1 and AC[int(p[i][0])-1][1]>i:
        WA=WA+1

print(k,WA)
### BUGGY CODE ###

n,p=map(int,input().split())
S=input()
s=int(S)
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=[0]*p
    for i in range(n):
        a=int(S[-i:])
        a%=p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    ruijo=1
    for i in range(n):
        ruijo%=p
        s+=int(S[-(i+1)])*(ruijo)
        a=s%p
        kouho[a]+=1
        ruijo*=10
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)
### BUGGY CODE ###

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * (10**i % 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)



### FIXED CODE ###

arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10, i, 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

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

#UnionFind木
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
        return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int, input().split())
  A[i] -= 1
  B[i] -= 1

ans = []

A = A[::-1]
B = B[::-1]
uf = UnionFind(N)
total = N*(N-1)//2
ans.append(total)
for i in range(M):
  if uf.same(A[i],B[i]):
    ans.append(total)
    continue
  m = len(uf.members(A[i]))
  n = len(uf.members(B[i]))
  uf.union(A[i],B[i])
  total -= m*n
  ans.append(total)
  
#print(ans)   

print(*ans[:-1][::-1], sep='\n')


### FIXED CODE ###

#UnionFind木
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def same(self, x, y):
        return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int, input().split())
  A[i] -= 1
  B[i] -= 1

ans = []

A = A[::-1]
B = B[::-1]
uf = UnionFind(N)
total = N*(N-1)//2
ans.append(total)
for i in range(M):
  if uf.same(A[i],B[i]):
    ans.append(total)
    continue
  m = abs(uf.parents[uf.find(A[i])])
  n = abs(uf.parents[uf.find(B[i])])
  #print(uf)
  #print(A[i]+1,m,B[i]+1,n)
  uf.union(A[i],B[i])
  total -= m*n
  ans.append(total)
  
#print(ans)   

print(*ans[:-1][::-1], sep='\n')
### BUGGY CODE ###

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

BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))

A.sort()

BC.sort(key=lambda x:x[1])

BC = [[bc[1]] * bc[0] for bc in BC]
BC = [flat_bc for bc in BC for flat_bc in bc]

for i in range(N):
    if A[i] < BC[-1]:
        A[i] = BC[-1]
        BC.pop()
        if not BC:
            break

print(sum(A))

### FIXED CODE ###

from collections import deque

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

BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))

A.sort()

BC.sort(key=lambda x:x[1], reverse=True)

D = deque([])
for bc in BC:
    b = bc[0]
    c = bc[1]

    for _ in range(b):
        D.append(c)

    if len(D) >= N: 
        break

for i in range(N):
    if A[i] < D[0]:
        A[i] = D[0]
        D.popleft()
        if not D:
            break

print(sum(A))
### BUGGY CODE ###

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

  def CalExVal(x):
      return (1/2*(x+1))
  #Ex = list((map(CalExVal, A)))
  temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  #for i in range(temp):
  #    adjlist[i] = sum(Ex[i:(K+i)])

  print(max(adjlist))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  #temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  tem = sum(Ex[:K])
  res = tem
  for i in range(0,N-K):
      tem = tem - Ex[i] + Ex[i+K]
      if res < tem:
      	res = tem
  print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
b=sorted(list(map(int,input().split())))
ma=10**13
mi=0
if sum(a)<k+1:
  print(0)
  quit()
while abs(ma-mi)>1:
  now=0
  for i in range(n):
    now+=max(0,(a[i]*b[i]-(mi+ma)//2+b[i]-1)//b[i])
  if now>k:
    mi=(ma+mi)//2
  else:
    ma=(ma+mi)//2
print(ma)

### FIXED CODE ###

import bisect
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
b=sorted(list(map(int,input().split())))
ma=a[0]*b[-1]
mi=0
if sum(a)<k+1:
  ma=0
for i in range(n):
  a[i]=a[i]*b[i]
while abs(ma-mi)>1:
  now=0
  for i in range(n):
    now+=max(0,(a[i]-(mi+ma)//2+b[i]-1)//b[i])
  if now>k:
    mi=(ma+mi)//2
  else:
    ma=(ma+mi)//2
print(ma)
### BUGGY CODE ###

l,r=map(int,input().split())
amari = 2018
for i in range(l, l+2020):
  for j in range(i+1, r+1):
    temp = (i*j)%2019
    if temp < amari:
      amari = temp
print(amari)

### FIXED CODE ###

l,r=map(int,input().split())
amari = 2018
if r-l > 2019:
  print(0)
else:
  for i in range(l, r+1):
    for j in range(i+1, r+1):
      temp = (i*j)%2019
      if temp < amari:
        amari = temp
     
  print(amari)
### BUGGY CODE ###

S = input()

from collections import defaultdict
mod = 2019
N = len(S)
D = defaultdict(int)
S = S[::-1]
ans = 0
T = [0]
D[0]+=1
for i in range(N):
    s = int(S[i])*pow(10,i)
    T.append((T[i]+s)%mod)
    ans += D[T[i+1]]
    D[T[i+1]]+=1
print(ans)

### FIXED CODE ###

S = input()

from collections import defaultdict
mod = 2019
N = len(S)
D = defaultdict(int)
S = S[::-1]
ans = 0
T = 0
D[0]+=1
for i in range(N):
    s = int(S[i])*pow(10,i,mod)
    T = (T+s)%mod
    ans += D[T]
    D[T]+=1
print(ans)
### BUGGY CODE ###

from itertools import takewhile

S = input()
total = 0
for idx in range(len(S) + 1):
    left = sum(1 for _ in takewhile(lambda x: x == "<", reversed(S[:idx])))
    right = sum(1 for _ in takewhile(lambda x: x == ">", S[idx:]))
    total += max((left, right))
print(total)


### FIXED CODE ###

S = input()
A = [0 for _ in range(len(S) + 1)]

for idx in range(len(S)):
    if S[idx] == "<":
        A[idx + 1] = max(A[idx + 1], A[idx] + 1)

for idx in reversed(range(len(S))):
    if S[idx] == ">":
        A[idx] = max(A[idx], A[idx + 1] + 1)

print(sum(A))
### BUGGY CODE ###

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

def xor(x, y):
    X = bin(max(x, y))
    Y = bin(min(x, y))
    s = len(X)
    l = len(Y)
    ans = ""
    for k in range(2, 2+s-l):
        ans += X[k]
    for i in range(2, l):
        ans += str(int(X[i+s-l]) ^ int(Y[i]))

    return int(ans, 2)


Ans = 0
mod = 10**9 + 7
for i in itertools.combinations(a, 2):
        Ans = (Ans + xor(i[0], i[1])) % mod
print(Ans)


### FIXED CODE ###

def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = tuple(map(int, input().split()))
mod = 10**9 + 7
cnt = [0] * 60
for i in range(n):
    r = a[i]
    for j in range(60):
        if r & 1:
            cnt[j] += 1
        r >>= 1

ans = 0
for i in range(60):
    ans += powmod(2, i, mod) * cnt[i] * (n-cnt[i])
    ans %= mod
print(ans)
### BUGGY CODE ###

import heapq

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

from operator import mul
from functools import reduce

def cmb(n, r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

heapq.heapify(A)

cmb_list = {}
for i in range(K-1, N):
    cmb_list[(i, K-1)] = cmb(i, K-1)

# print(A)

max_f = 0
min_f = 0


for idx in range(N):
    a = heapq.heappop(A)
    if idx >= K-1:
        max_f += cmb_list[(idx, K-1)]*a
        # print("max", cmb(idx, K-1), idx, K-1, a)

    if N-(idx+1) >= K - 1:
        min_f += cmb_list[(N-(idx+1), K-1)]*a
        # print("min", cmb(N-(idx+1), K-1), N-(idx+1), K-1, a)

print((max_f - min_f) % (10**9+7))

### FIXED CODE ###

import heapq

n, K = map(int, input().split())
A = list(map(int, input().split()))

from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

def mpow(a, n):
    if n == 0: return 1
    if n == 1: return a % MOD
    if n % 2 == 1: return (a % MOD * mpow(a, n - 1) % MOD) % MOD
    t = mpow(a, n // 2)
    return (t * t) % MOD

fac = [1] * (n + 1)
inv_fac = [1] * (n + 1)
for i in range(n):
    fac[i + 1] = (fac[i] * (i + 1)) % MOD
inv_fac[n] = mpow(fac[n], MOD - 2)
for i in range(n, 0, -1):
    inv_fac[i - 1] = (inv_fac[i] * i) % MOD

def cmb(n, r):
    if n == 0 and r == 0: return 1
    if n < r or n < 0: return 0
    return (fac[n] * (inv_fac[r] * inv_fac[n - r]) % MOD) % MOD

A.sort()

# cmb_list = {}
# cmb_list[(K - 1, K - 1)] = cmb(K - 1, K - 1)
# for i in range(K, n):
#     cmb_list[(i, K-1)] = cmb_list[(i-1, K-1)] * i // (i - (K - 1))

max_f = 0
min_f = 0

for idx in range(n):
    a = heapq.heappop(A)
    if idx >= K - 1:
        max_f += cmb(idx, K - 1) * a
        # print("max", cmb(idx, K-1), idx, K-1, a)

    if n - (idx + 1) >= K - 1:
        min_f += cmb(n - (idx + 1), K - 1) * a
        # print("min", cmb(N-(idx+1), K-1), N-(idx+1), K-1, a)

print((max_f - min_f) % (10**9+7))
### BUGGY CODE ###

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

ac = []
wa = {}

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC":
        ac.append(p_i)
    elif s_i == "WA":
        if p_i not in ac:
            if p_i not in wa.keys():
                wa[p_i] = 1
            else:
                wa[p_i] += 1
                
ac = set(ac)
wa = [count for p_i, count in wa.items() if p_i in ac]

print(len(ac), sum(wa))

### FIXED CODE ###

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

ac = 0
wa = 0
ac_status = [0 for i in range(N)]
wa_status = [0 for i in range(N)]

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC" and ac_status[int(p_i) - 1] == 0:
        ac += 1
        ac_status[int(p_i) - 1] += 1
        wa += wa_status[int(p_i) - 1]
    if s_i == "WA":
        wa_status[int(p_i) - 1] += 1

print(ac, wa)
### BUGGY CODE ###

import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

array = [0, 0, 0]

s = int(input())
sum = 0
for a in range(1, s+1):
    for b in range(1, s+1):
        for c in range(1, s+1):
            array = [a, b, c]
            sum += gcd_list(array)

print(sum)

### FIXED CODE ###

import math
from functools import reduce
import numpy as np
from itertools import combinations
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

s = int(input())
qwe = np.arange(s+1)

sum = (1+s)*s/2

for i in range(1, s+1):
    for j in range(i + 1, s+1):
        sum += gcd(i, j, j) * 3
        sum += gcd(i, i, j )* 3
        # print(i, j)
        for k in range(j + 1, s+1):
            sum += gcd(i, j, k) * 6
            # print(i, j, k)
print(int(sum))
### BUGGY CODE ###

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)



### FIXED CODE ###

n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=(dp_1[i-1][j]+dp_1[i-1][j-a_list[i]])%mod
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]%mod
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for h in range(n):
    b = a[:h] + a[h+1:]
    print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = tuple(a)
a.sort()
for i in b:
    if i == a[n-1]:
        print(a[n-2])
    else:
        print(a[n-1])
### BUGGY CODE ###

# %%

n, m = list(map(int, input().split()))
ary = list(map(int, input().split()))
bry = list(map(int, input().split()))
mod = 10 ** 9 + 7


# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    cnt = 1
    for i in range(n * m, 0, -1):
        if (i in ary) & (i in bry):
            pass
        elif (i in ary) ^ (i in bry):
            if i in ary:
                cnt *= len([b for b in bry if i < b]) % mod
            else:
                cnt *= len([a for a in ary if i < a]) % mod
        else:
            nn = len([a for a in ary if i < a])
            nm = len([b for b in bry if i < b])
            cnt *= (nn * nm - (n * m - i)) % mod

    print(cnt % mod)


### FIXED CODE ###

import sys

# %%

n, m = list(map(int, sys.stdin.readline().split()))
ary = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
bry = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)
mod = 10 ** 9 + 7

# %%

if len(set(ary)) != len(ary) or len(set(bry)) != len(bry):
    print(0)

else:
    ary.append(0)
    bry.append(0)

    cnt = 1
    i = 0
    j = 0
    for num in range(n * m, 0, -1):

        if (num == ary[i]) and (num == bry[j]):
            i += 1
            j += 1

        elif (num == ary[i]) or (num == bry[j]):
            if num == ary[i]:
                cnt *= len(bry[:j])
                i += 1
            else:
                cnt *= len(ary[:i])
                j += 1

        else:
            # na = len(ary[:i])
            # nb = len(bry[:j])
            cnt *= (i * j - (n * m - num))

        cnt = cnt % mod

    print(cnt)
### BUGGY CODE ###

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

ap=a[0]
for i in range(1,n):
    ap=ap*a[i]
    
if ap<=10**18:
    print(ap)
else:
    print(-1)

### FIXED CODE ###

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

def mp(a):
    b=[]
    if len(a)==1:
        b.append(a[0]) 
    elif len(a)%2==0:
        for i in range(0,len(a),2):
            b.append(a[i]*a[i+1]) 
    else:
        for i in range(0,len(a)-1,2):
#            print(i)
            b.append(a[i]*a[i+1]) 
#        print("1",a[len(a)//2+1])
        b.append(a[len(a)-1]) 
    return b

c=aa.copy()
while len(c)>1:
    c=mp(c)   
#    print(c)
    
if c[0]<=10**18:
    print(c[0])
else:
    print(-1)
### BUGGY CODE ###

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

A_div = [0 for _ in range(N)]
answer = 0
for i in range(N):
    if A_div[i] == 0:
        for j in range(i + 1, N):
            if A[i] % A[j] == 0:
                A_div[i] += 1
            if A[j] % A[i] == 0:
                A_div[j] += 1
    
    if A_div[i] == 0:
        answer += 1

print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
A_div = [0] * (10 ** 6 + 1)

for a in A:
    A_div[a] += 1
    if A_div[a] == 1:
        for j in range(2 * a, 10 ** 6 + 1, a):
            A_div[j] += 100

print(A_div.count(1))