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

N = int(input())
A = [0] * N
A = list(map(int,input().split()))

ans = 0
mod = 10**9+7
# for i in range(N-1):
#     for j in range(i+1,N):
#         ans += (A[i]%mod) * (A[j]%mod)
#         ans %= mod

A = list(map(lambda x: x %mod,A))
for i in range(N-1):
    for j in range(i+1,N):
        ans += (A[i]) * (A[j])
        ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * (N+1)

# 累積和を使う
for i in range(1,N+1):
    B[i] = A[i-1]+B[i-1]
# 累積和の配列完成
# print(B) 

ans = 0
MOD = 10**9+7
for i in range(N):
    ans += A[i] * (B[N] - B[i+1])
    ans %= MOD
print(ans)
### BUGGY CODE ###

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][S]=1
for i in range(1,N+1):
  for j in range(math.ceil(S/2),S+1):
    if j+A[i-1] <= S:
      dp[i][j] = dp[i-1][j+A[i-1]]*2 + dp[i-1][j]
    else:
      dp[i][j] = dp[i-1][j]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right
import numpy as np

n, d, a = map(int, input().split())
xh=[list(map(int, input().split())) for _ in range(n)]
xh.sort()
xh = [list(x) for x in zip(*xh)]
l = 0
ret = 0
while l < n:
    xl = xh[0][l]
    hl = xh[1][l]
    l += 1
    if hl <= 0:
        continue
    r = bisect_right(xh[0], xl+2*d)
    k = (hl+(a-1))//a
    ret += k
    for i in range(l, r):
        xh[1][i] -= k * a
print(ret)


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right

n, d, a = map(int, input().split())
x = []
xh = dict()
for _ in range(n):
    xi, hi = map(int, input().split())
    x.append(xi)
    xh[xi] = hi
x.sort()

l = 0
ret = 0
ai = [0] * (n+1)
anow = 0
while l < n:
    xl = x[l]
    hl = xh[xl]
    anow += ai[l]
    hl -= a * anow
    if hl > 0:
        r = bisect_right(x, xl+2*d)
        k = (hl+(a-1))//a
        ret += k
        anow += k
        ai[r] -= k
    l += 1
print(ret)
### BUGGY CODE ###

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    res=0
    for u,v,w in es:
        used=False
        for i in range(n):
            for j in range(i+1,n):
                if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                    used=True
        if not used:
            res+=1
    print(res)


### FIXED CODE ###

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))
### BUGGY CODE ###

n, a, b = list(map(int, input().split(' ')))
tmp = 0
count = 0
if a == 0:
    print(0)
else:
    while count < 10**100:
        n -= a
        tmp += a
        if n <= 0:
            print(tmp + n)
            break
        n -= b
        if n <= 0:
            print(tmp)
            break
    

### FIXED CODE ###

n, a, b = list(map(int, input().split(' ')))
if a == 0:
    print(0)
elif n % (a+b) <= a:
    print(a*(n // (a+b))+ n % (a+b))
else:
    print( a*(n // (a+b))+a)
### BUGGY CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
#宝石を取る取らない
def dfs(A):
    global ans
    # 終端条件 --- N 重ループまで回したら処理して打ち切り
    if len(A) == N:
        D=jg(A)
        if ans<D:
          ans=D
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

#コスト算出
def jg(A):
  X=0
  Y=0
  for i in range(N):
    if A[i]==1:
      X+=V[i]
      Y+=C[i]
  d=X-Y
  return d
dfs([])
print(ans)

### FIXED CODE ###

N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0

for i in range(N):
  if V[i] > C[i]:
    ans += V[i]-C[i]
print(ans)
### BUGGY CODE ###

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

n, m, k = map(int, input().split())
FRIENDS = [[0]*n for _ in range(n)]
BLOCKS = [[0]*n for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIENDS[a][b] = FRIENDS[b][a] = 1
    uf.union(a, b)


for _ in range(k):
    c, d = map(lambda x: int(x)-1, input().split())
    BLOCKS[c][d] = BLOCKS[d][c] = 1


ans = []


for i in range(n):
    c_friends = sum(FRIENDS[i])
    blocks = BLOCKS[i]
    c_member = uf.count_member(i)
    c_blocks = 0
    for j, b in enumerate(blocks):
        if b:
            if uf.find(i) == uf.find(j):
                c_blocks += 1
    ans.append(c_member - 1 - c_friends - c_blocks)

print(*ans)

### FIXED CODE ###

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

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

class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        self.c = None

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

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

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    if S[i] == 'G':
        G.append(i)
    if S[i] == 'B':
        B.append(i)

colors = [
    [R, G, B],
    [R, B, G],
    [G, R, B],
    [G, B, R],
    [B, R, G],
    [B, G, R],
]

ans = 0

for C1, C2, C3 in colors:
    for c1 in C1:
        for c2 in C2:
            if c1 > c2:
                continue
            ans += len([c3 for c3 in C3 if c3 > c2 and abs(c3-c2) != abs(c2-c1)])

print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N = ii()
S = si()

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt * g_cnt * b_cnt

for i in range(N):
    for dist in range(N):
        j = i + dist
        k = j + dist
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            ans -= 1

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

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
L=seachPrimeNum(100000)
R=[i for i in L if (i+1)//2 in L]
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  print(len([i for i in R if i>=a and i<=b]))

### FIXED CODE ###


def primes(n):
    candidate = list(range(2, n+1))
    prime = []
    limit = n**0.5 + 1
    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate)
            break
        prime.append(p)

        candidate = [i for i in candidate if i % p != 0]
    return prime
L=primes(100000)
R=set([i for i in L if (i+1)//2 in L])
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  print(len([i for i in R if i>=a and i<=b]))
### BUGGY CODE ###

N = int(input())
power = 1

for i in range(1,N+1):
    power *= i

print(power % (10**9+7))


### FIXED CODE ###

N = int(input())
power = 1

for i in range(1,N+1):
    power = power * i % 1000000007

print(power)
### BUGGY CODE ###

k,s = map(int,input().split())
#x + y + z = s z < k
counter = 0
for i in range(k + 1):
    if i > s:
        break
    for j in range(k + 1):
        if  i + j > s :
            break
        for l in range(k + 1):
            if i + j + l > s:
                break
            if l > k:
                break
            if i + j + l == s:
                #print(i,j,l)
                counter += 1

print(counter)


### FIXED CODE ###

k,s = map(int,input().split())
#x + y + z = s z < k
counter = 0
for i in range(k + 1):
    for j in range(k + 1):
        z = s - i - j
        if 0 <= z and z <= k:
            counter += 1

print(counter)
### BUGGY CODE ###

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))

        while q:
            y, x, v = q.popleft()
            m[y][x] = v
            for dj, di in ((y, x + 1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                if ans < v+1:
                    ans = v+1
print(ans)


### FIXED CODE ###

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

import bisect

n,m = map(int,input().split())
l = list(map(int,input().split()))
b_c = [list(map(int,input().split())) for i in range(m)]

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

idx = 0
ans = 0

for i in range(m):
    if idx == n:
        break
    if l[idx:][0] >= b_c[i][1]:
        break
    
    temp = bisect.bisect_left(l[idx:],b_c[i][1])
    if temp > b_c[i][0]:
        temp = b_c[i][0]
    if temp > (n-idx-1):
        temp = n-idx
    ans += temp*b_c[i][1]
    idx += temp

ans += sum(l[idx:])
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

n,m = map(int,input().split())
heap = []

for i in map(int,input().split()):
    heappush(heap,i)

bc = [list(map(int, input().split())) for _ in range(m)]
bc.sort(key = lambda x: -x[1])

for b,c in bc:
    for j in range(b):
        a = heappop(heap)
        if a < c:
            heappush(heap,c)
        
        else:
            heappush(heap, a)
            break
        
print(sum(heap))
### BUGGY CODE ###

def resolve():
    n, a, b = map(int, input().split())

    all = 2 ** n

    mod = 10**9+7 #出力の制限
    N = n
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )

    def combinations_count(n, r, mod):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod

    all -= combinations_count(n, a, mod)
    all -= combinations_count(n, b, mod)

    if n==2 and a != b:
        print(0)
        return 

    print(all - 1)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def mod_inverse(a, p):
    return pow(a, p-2, p)  # フェルマーの小定理より

def mod_binominal(n, r, p):
    numerator= 1
    for i in range(r):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, r+1):
        denominator = (denominator * i) % p

    return (numerator * mod_inverse(denominator, p)) % p

def resolve():
    n, a, b = map(int, input().split())
    p = 10**9+7

    ans = pow(2, n, p) - mod_binominal(n, a, p) - mod_binominal(n, b, p) - 1
    print((ans + p) % p)


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

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import math


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
C = []

for _ in range(N):
    x, y = map(int, input().split())
    C.append((x, y))

r_large = 800.
r_small = 0.
r = (r_large + r_small) / 2.

for _ in range(100):
    isValid = True
    r2 = (r * 2.)**2.
    for i in range(N):
        for j in range(N):
            l = (C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2
            if l > r2:
                isValid = False
                break

            nx, ny = (C[i][0]+C[j][0])/2., (C[i][1]+C[j][1])/2.

            for k in range(N):
                l2 = (C[k][0] - nx) ** 2 + (C[k][1] - ny) ** 2
                if l2 > r2:
                    isValid = False
                    break

        if not isValid:
            break

    if isValid:
        r_large = r
    else:
        r_small = r

    r = (r_large + r_small) / 2.

print(r)

#print(math.sqrt(lm) / 2.)


### FIXED CODE ###

import math
import sys
import itertools
sys.setrecursionlimit(10 ** 7)

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

N = int(input())
XY = [[float(x) for x in input().split()] for _ in range(N)]

ans = 1500.
eps = 10. ** -8


def circumcenter(A, B, C):
    ax = A[0]
    ay = A[1]
    bx = B[0]
    by = B[1]
    cx = C[0]
    cy = C[1]
    d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by))

    if d == 0.:
        return None

    ux = ((ax * ax + ay * ay) * (by - cy) + (bx * bx + by * by)
          * (cy - ay) + (cx * cx + cy * cy) * (ay - by)) / d
    uy = ((ax * ax + ay * ay) * (cx - bx) + (bx * bx + by * by)
          * (ax - cx) + (cx * cx + cy * cy) * (bx - ax)) / d
    return (ux, uy)


def check(center_x, center_y, R2):
    ok = True
    for x, y in XY:
        d = (center_x - x) ** 2. + (center_y - y) ** 2.
        if R2 + eps < d:
            ok = False
            break

    return ok


# 2点
for i, j in itertools.combinations(range(N), 2):
    ax, ay = XY[i]
    bx, by = XY[j]

    center_x = (ax + bx) / 2.
    center_y = (ay + by) / 2.
    R2 = (ax - center_x) ** 2 + (ay - center_y) ** 2
    R = math.sqrt(R2)

    if check(center_x, center_y, R2):
        ans = min(R, ans)


# 3点
for a, b, c in itertools.combinations(range(N), 3):
    d = circumcenter(XY[a], XY[b], XY[c])

    if d is None:
        continue

    center_x = d[0]
    center_y = d[1]

    ax = XY[a][0]
    ay = XY[a][1]
    R2 = (ax - center_x) ** 2. + (ay - center_y) ** 2.
    R = math.sqrt(R2)

    ok = check(center_x, center_y, R2)

    if check(center_x, center_y, R2):
        ans = min(ans, R)

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

charseq = raw_input()
start = -1
end = -1

for i in range(len(charseq)):
    for j in xrange(i+2, len(charseq)+1):
        part = charseq[i:j]
        chars = list(part)
        for char in chars:
            if chars.count(char) > (j-i)/2:
                start = i+1 
                end = j 
                break
        if not start == -1: 
            break
    
print start, end 
    


### FIXED CODE ###

charseq = raw_input()
start = -1
end = -1

for i in range(len(charseq)-1):
    if charseq[i] == charseq[i+1]:
        start = i+1 
        end = i+2 
        break
if start == -1: 
    for i in range(len(charseq)-2):
        if charseq[i] == charseq[i+2]:
            start = i+1 
            end = i+3 
            break

print start, end
### BUGGY CODE ###

from collections import deque
N = int(input())
A = [int(i) for i in input().split()]

s = deque()
for i in range(N):
    s.append(str(A.index(i+1)+1))

ans = ' '.join(s)
print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(i) for i in input().split()]
values = [str(i+1) for i in range(N)]
dic = {key: val for key, val in zip(A, values)}
dic_s = deque(sorted(dic.items()))
s =deque()
for i in range(N):
    s.append(dic_s[i][1])

ans = ' '.join(list(s))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

Cn = [0]*(N+1)

for i,Ai in enumerate(An):
    if i == 0:
        Cn[i+1] = Ai
    else:
        Cn[i+1] = Cn[i] + Ai

def func(n):
    if n <= 1:
        return 1
    else:
        tmp = 1
        for i in range(1,n+1):
            tmp = tmp * i
        return tmp

mod = {}
for i in range(N+1):
    if Cn[i]%M in mod:
        mod[Cn[i]%M] += 1
    else:
        mod[Cn[i]%M] = 1

ans = 0
for val in mod.values():
    if val <= 1:
        continue
    elif val == 2:
        ans += 1
    else:
        tmp = func(val) / (func(2) * func(val - 2))
        ans += int(tmp)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

Cn = [0]*(N+1)

for i,Ai in enumerate(An):
    if i == 0:
        Cn[i+1] = Ai
    else:
        Cn[i+1] = Cn[i] + Ai

# def func(n):
#     if n <= 1:
#         return 1
#     else:
#         tmp = 1
#         for i in range(2,n+1):
#             tmp = tmp * i
#         return tmp

mod = {}
for i in range(N+1):
    if Cn[i]%M in mod:
        mod[Cn[i]%M] += 1
    else:
        mod[Cn[i]%M] = 1

ans = 0
for val in mod.values():
    if val <= 1:
        continue
    elif val == 2:
        ans += 1
    else:
        # tmp = func(val) / (func(2) * func(val - 2))
        tmp = combinations_count(val,2)
        ans += int(tmp)

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

num = int(input())

value = list(map(int, input().split()))

ans = 1
for i in value:
    ans *= i
    
if ans > 10 ** 18:
    ans = -1
    
print(ans)

### FIXED CODE ###

num = int(input())

value = list(map(int, input().split()))

if 0 in value:
    print(0)
    exit()

ans = 1
for i in value:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit()
    
print(ans)
### BUGGY CODE ###

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

cnt = 0
for i in range(len(P)):
  cnt += 1
  for j in range(i):
    if P[i] > P[j]:
      cnt -= 1
      break

print(cnt)

### FIXED CODE ###

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

cnt = 1
min_p = P[0]
for i in range(1, len(P)):
  if P[i] < min_p:
    cnt += 1
    min_p = P[i]

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

m,w = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(m)]

dp = [[0]*(w+1) for _ in range(m+1)]

# 初期値を調整
for w_i in range(1, w+1):
  dp[0][w_i] = float("-inf")
  
for w_i in range(w+1):
  for m_i in range(1, m+1):
    if w_i-WV[m_i-1][0]>=0:
      dp[m_i][w_i] = max(dp[m_i-1][w_i], dp[m_i-1][w_i-WV[m_i-1][0]]+WV[m_i-1][1])
    else:
      dp[m_i][w_i] = dp[m_i-1][w_i]

      
print(max(dp[-1]))

### FIXED CODE ###

m,w = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(m)]

dp = [[0]*(w+1) for _ in range(m+1)]

# 初期値を調整
for w_i in range(1, w+1):
  dp[0][w_i] = float("-inf")
  
for w_i in range(w+1):
  for m_i in range(1, m+1):
    if w_i-WV[m_i-1][0]>=0:
      dp[m_i][w_i] = max(dp[m_i-1][w_i], dp[m_i-1][w_i-WV[m_i-1][0]]+WV[m_i-1][1])
    else:
      dp[m_i][w_i] = dp[m_i-1][w_i]

      
print(max(dp[-1]))
### BUGGY CODE ###

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

def factorization(n):
    arr, temp = [], n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

fac = [0] * N
for i in range(N):
    if a[i]%2==0:
        arr = factorization(a[i])
        fac[i] = arr[0][1]

print(sum(fac))

### FIXED CODE ###

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

def factorization(n):
    cnt = 0
    while n%2==0:
        n /= 2
        cnt += 1
    return cnt

fac = [0] * N
for i in range(N):
    if a[i]%2==0:
        fac[i] = factorization(a[i])

print(sum(fac))