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

import sys
input = sys.stdin.readline
sList, tList = list(input()), list(input())

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0
for i, s in enumerate(sList, start=1):
    index = i % 2
    sameStr = ""
    for j, t in enumerate(tList, start=1):
        aboveStr = dp[index-1][j]
        if s == t:
            sameStr = dp[index-1][j-1] + s
        dp[index][j] = sameStr if len(sameStr) > len(aboveStr) else aboveStr

print(dp[index][-1])


### FIXED CODE ###

sList, tList = list(input()), list(input())

dp = [[0] * (len(tList) + 1) for _ in range(len(sList) + 1)]
for i, s in enumerate(sList, start=1):
    sameNum = 0
    for j, t in enumerate(tList, start=1):
        num = dp[i-1][j]
        if s == t:
            sameNum = max(num, dp[i-1][j-1] + 1)
        dp[i][j] = max(num, sameNum)

ans = ""

while(i > 0, j > 0):
    num = dp[i][j]
    if num == 0:
        break
    if sList[i-1] == tList[j-1]:
        ans = sList[i-1] + ans
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1

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

def main():
    a,b = map(int,input().split())
    leg  = 0
    for i in range(2**(a)):
        leg = 0
        for j in range(a):
            if (i & 1 <<j):
                leg +=4
            else:
                leg +=2
        if leg == b:
            print('Yes')
            exit()
    print('No')
main()

### FIXED CODE ###

a,b = map(int,input().split())
leg  = 0
for i in range(0,a+1):
    if 2*i +4*(a-i) == b:
        print('Yes')
        exit()
print('No')
### BUGGY CODE ###

from sys import stdin


S = stdin.readline().rstrip()
T = stdin.readline().rstrip()

N = len(S)

ret = "Yes"

for i in range(0, N):
    if ret == "No":
        break

    for j in range(i+1, N):
        if S[i] == S[j]:
            if T[i] != T[j]:
                ret = "No"
        if T[i] == T[j]:
            if S[i] != S[j]:
                # print("type2:",i,j, S[j],T[j])
                ret = "No"

print(ret)

### FIXED CODE ###

S = input()
T = input()

d1 = dict()
d2 = dict()

ret = "Yes"

for s, t in zip(S, T):
    #print("{}-->{}".format(s, t))
    tmp1 = d1.get(s, None)
    tmp2 = d2.get(t, None)
    if (tmp1 == None or tmp1 == t) and (tmp2 == None or tmp2 == s):
        d1[s] = t
        d2[t] = s
    else:
        ret = "No"

print(ret)
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
AClist = []

for i in range(Q):
  l, r = map(int, input().split())
  result = 0
  for j in range(l - 1, r - 1):
    if(s[j:j + 2] == "AC"): result += 1
  print(result)

### FIXED CODE ###

N, Q = map(int, input().split())
s = input()
AClist = [0] * N

for i in range(N - 1):
  AClist[i + 1] = AClist[i] + int(s[i:i + 2] == "AC")
  
for i in range(Q):
  l, r = map(int, input().split())
  print(AClist[r - 1] - AClist[l - 1])
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  B = []
  for i in range(h):
    row = list(map(int, input().split()))
    A.append(row)
  for i in range(h):
    row = list(map(int, input().split()))
    B.append(row)
 
  dp = [[set([]) for j in range(w+1)] for i in range(h+1)]
  dp[0][0].add(abs(A[0][0] - B[0][0]))
  for i in range(h):
    for j in range(w):
      for item in dp[i][j]:
        if j < w - 1:
          dif = abs(A[i][j+1] - B[i][j+1])
          dp[i][j+1].add(item+dif)
          dp[i][j+1].add(abs(item-dif))
        if i < h - 1:
          dif = abs(A[i+1][j] - B[i+1][j])
          dp[i+1][j].add(item+dif)
          dp[i+1][j].add(abs(item-dif))
  print(min(dp[h-1][w-1]))
if __name__ == '__main__':
  main()


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import fractions

"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f


def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = A[0]
    for i in range(1, n):
        l = lcm(l, A[i])
    res = 0
    
    for a in A:
        res += l//a
        res %= mod
    print(res%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import functools
"""最大公約数"""
def gcd(a,b):
    import fractions
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f

def m(nums):
    return functools.reduce(lcm, nums)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = m(A)
    res = 0
    print(sum(l// i for i in A) % mod)

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

import itertools
import numpy as np
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]

cnt = 0
for i in range(1, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
import numpy as np
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, a = imap()
x = np.array(iarr()) - a
MAX = 50*50+1

dp = np.zeros((n+1, 2*MAX+1)).astype(int)
dp[0][MAX] = 1
for i in range(n):
    for j in range(2*MAX):
        if j-x[i] < 0 or j-x[i] > 2*MAX:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x[i]]
print(dp[n][MAX]-1)
### BUGGY CODE ###

from collections import defaultdict,deque
import bisect

N = int(input())
A = list(map(int,input().split()))
graph = defaultdict(deque)
for _ in range(0,N-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

arrive = [False] * (N+1)
dp_dict = [None] * N
dp_dict[0] = [A[0]]

ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].pop()
            if arrive[w] == False:
                tar = A[w-1]
                dp = dp_dict[v-1].copy()
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w-1] = dp
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1
for i in ans[1::]:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 1)
 
def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in graph[s]:
        if t == parent:
            continue
        DFS(t, s)
    LIS[i] = v
    return
 
DFS(1)
print(*ans[1:], sep="\n")
### BUGGY CODE ###

import math
def is_prime(x):
  if x == 1:
    return False
  for i in range(2, x):
    if x % i == 0:
      return False
    if i * i>= x:
      break         #breakにしないと膨大な数字をいつまでも追いかけている
  return True

def check(l,r):
  count = 0
  for i in range(l,r+1,2):
    if is_prime(i) == True and is_prime((i+1)//2) == True:
      count += 1
  return count


Q = int(input())

nums = []
for i in range(Q):
  l,r = map(int,input().split())
  nums.append(check(l,r))


for i in nums:
  print(i)

### FIXED CODE ###

NMAX = 10**5+1

is_prime = [True]*NMAX
for i in range(2, NMAX):
    if is_prime[i]:
        for j in range(2*i, NMAX, i):
            is_prime[j] = False

sim_2017 = [0]*NMAX
for i in range(3, NMAX, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        sim_2017[i] += 1
for i in range(1, NMAX):
    sim_2017[i] += sim_2017[i-1]

q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    ans = sim_2017[r] - sim_2017[l-1]
    print(ans)
### BUGGY CODE ###

import sys
import bisect
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

A, B = tuple(li())

nums = range(A, B + 1)
L = len(format(B, 'b'))
res = [0] * L
for num in nums:
    # print(f"num:{num}")
    bit = 1
    for i in range(L):
        # print(f"i:{i}")
        cur_bit = num & bit
        if cur_bit == bit:
            res[i] ^= 1
        bit = bit << 1
        # print(f"res_bit:{res}")
    # print(f"res:{res}")
res = reversed(res)
res_num = int("".join(map(str, res)), 2)
print(res_num)


### FIXED CODE ###

import sys
import bisect
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

A, B = tuple(li())

def F(num):
    if num == 0:
        return 0
    # there are a pair: (0,1), (2,3)... where xor in every pair is 1
    a = (num + 1) // 2
    ret = 0 if a % 2 == 0 else 1
    ret = ret ^ num if num % 2 == 0 else ret
    return ret
res = F(A - 1) ^ F(B)
print(res)
### BUGGY CODE ###

N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		g = i ** N
		if g > P:
			break
		if P % g == 0:
			ans = i
	print(ans)

### FIXED CODE ###

import math	
N, P = map(int, input().split())
if N == 1:
	print(P)
else:
	ans = 1
	for i in range(2, P):
		if N * math.log(i) > math.log(P):
			break
		if P % (i ** N) == 0:
			ans = i
	print(ans)
### BUGGY CODE ###

x,k,d=input().split()
x=int(x)
k=int(k)
d=int(d)
if(abs(x)>k*d):
    print(abs(x)-k*d)
else:
    for i in range(k):
        x=abs(x)-d
        if(x<1):
            break
    k=k-i-1
    if(k==0):
        print(abs(x))
    elif(k%2==0):
        print(abs(x))
    else:
        print(abs(x+d))
        

### FIXED CODE ###

x,k,d=input().split()
x=int(x)
k=int(k)
d=int(d)
if(abs(x)>k*d):
    print(abs(x)-k*d)
else:
    i=abs(x)//d
    a=abs(x)%d
    k=k-i
    if(k==0):
        print(a)
    elif(k%2==0):
        print(a)
    else:
        print(abs(a-d))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

import bisect
a = [0,0,n+1,n+1]
ans = 0
for tmp in p_ind:
    val, i = tmp
    j = bisect.bisect(a,i)
    ans += ((a[j+1] - a[j])* (i - a[j-1]) + (a[j] - i)* (a[j-1] - a[j-2])) * val
    a.insert(j,i)

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
p_ind = [ (p[i], i+1) for i in range(n) ]
p_ind.sort(reverse=True)

# 平方分割します。
max_n = 10**5
div_n = int(max_n**(1/2))+1
a = [[] for _ in range(div_n)]
a[0] = [0,0]
a[(n+1)//div_n].append(n+1)
a[(n+1)//div_n].append(n+1)
a_count = [0] * (div_n)
a_count[0] += 2
a_count[(n+1)//div_n] += 2

import bisect
ans = 0
for tmp in p_ind:
    val, i = tmp
    group = i//div_n
    j = bisect.bisect(a[group],i)
    #left
    if(j>1):
        left1 = a[group][j-1]
        left2 = a[group][j-2]
    elif(j==1):
        left1 = a[group][j-1]
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        left2 = a[lg][-1]
    else:
        lg = group-1
        while(True):
            if(a_count[lg]>0):
                break
            lg -=1
        if(a_count[lg]>=2):
            left1 = a[lg][-1]
            left2 = a[lg][-2]
        else:
            left1 = a[lg][-1]
            while(True):
                lg -=1
                if(a_count[lg]>0):
                    break
            left2 = a[lg][-1]
    #right
    if(a_count[group]>=j+2):
        right1 = a[group][j]
        right2 = a[group][j+1]
    elif(a_count[group]>=j+1):
        right1 = a[group][j]
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        right2 = a[rg][0]
    else:
        rg = group
        while(True):
            rg += 1
            if(a_count[rg]>0):
                break
        if(a_count[rg]>=2):
            right1 = a[rg][0]
            right2 = a[rg][1]
        else:
            right1 = a[rg][0]
            while(True):
                rg += 1
                if(a_count[rg]>0):
                    break
            right2 = a[rg][0]

    ans += ((right2 - right1)* (i - left1) + (right1 - i)* (left1 - left2)) * val
    a[group].insert(j,i)
    a_count[group] += 1

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

#!/usr/bin/env python3

import math
def cmb(n, a, p):
    ans = 1
    for i in range(a):
        ans *= (n-i)
    return (ans // math.factorial(a)) % p
    
n,a,b = map(int,input().split())
mod = 10**9 + 7
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod
print((pow(n,2,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)


### FIXED CODE ###

#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M=map(int,input().split())
list1=list(map(int,input().split()))
for _ in range(M):
  B,C=map(int,input().split())
  if len(list1)<N or min(list1)<C:
    list1+=[C]*B
    if len(list1)>N:
      for i in range(len(list1)-N):
        list1.remove(min(list1))
SUM=sum(list1)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
### BUGGY CODE ###

#Make a Rectangle
N = int(input())
A = list(map(int, input().split()))
 
a = sorted(list(set(A)), reverse=True)
b = []
for ai in a:
    c = A.count(ai)
    for i in range(c//2):
        b.append(ai)
    if (len(b)>=4):
        break
 
if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])

### FIXED CODE ###

#Make a Rectangle
N = int(input())
A = list(map(int, input().split()))

a = sorted(A, reverse=True)
b = []

i = 0
while i<N-1:
    if ( a[i]==a[i+1] ):
        b+=[a[i]]
        i+=2
    else:
        i+=1
    if (len(b)>1):
        break

if (len(b)<2):
    print(0)
else:
    print(b[0]*b[1])
### BUGGY CODE ###

def Qb():
    n = int(input())
    lina = map(int, input().split())

    ans = 1
    for i, a in enumerate(lina):
        ans = a * ans
    if 10 ** 18 < ans:
        ans = -1
    print(ans)


if __name__ == '__main__':
    Qb()


### FIXED CODE ###

def Qb():
    n = int(input())
    lina = list(map(int, input().split()))

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

    ans = 1
    for a in lina:
        ans *= a
        if 10 ** 18 < ans:
            ans = -1
            break
    print(ans)

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

import itertools
K,S=map(int,input().split())
ans=0
l=[]

for i in range(K+1):
    for j in range(i+1):
        for k in range(j+1):
            if i+j+k==S:
                l.append([i,j,k])
                break
L=[]
for c in l:
    for a in itertools.permutations(c):
        L.append(a)

print(len(set(L)))

### FIXED CODE ###

import itertools

K,S=map(int,input().split())

ans=0
for i in range(K+1):
  for j in range(K+1):
    if 0<=S-(i+j)<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

l = input().split()
H = int(l[0])
W = int(l[1])

S = []
for i in range(H):
    l = input().split()
    S.append(l[0])

# print(H, W, S)

# TS = []
# for i in range(W):
#     tmp = ''
#     for j in range(H):
#         tmp += S[j][i]
#     TS.append(tmp)

# print(TS)

HL = []
for i in range(H):
    l = 0
    begin = 0
    tmp = []
    for j in range(W):
        if S[i][j] == '.':
            l += 1
        else:
            tmp.extend([l]*(j - begin))
            tmp.append(0)
            begin = j + 1
            l = 0
    if begin != W:
        tmp.extend([l]*(W - begin))
    HL.append(tmp)

WL = []
for i in range(W):
    l = 0
    begin = 0
    tmp = []
    for j in range(H):
        if S[j][i] == '.':
            l += 1
        else:
            tmp.extend([l]*(j - begin))
            tmp.append(0)
            begin = j + 1
            l = 0
    if begin != H:
        tmp.extend([l]*(H - begin))
    WL.append(tmp)

max_l = 0
for i in range(H):
    for j in range(W):
        l = HL[i][j] + WL[j][i]
        max_l = max(l, max_l)
print(max_l - 1)


### FIXED CODE ###

l = input().split()
H = int(l[0])
W = int(l[1])

S = []
for i in range(H):
    l = input().split()
    S.append(l[0])

# print(H, W, S)

# TS = []
# for i in range(W):
#     tmp = ''
#     for j in range(H):
#         tmp += S[j][i]
#     TS.append(tmp)

# print(TS)

HL = []
for i in range(H):
    l = 0
    begin = 0
    tmp = []
    for j in range(W):
        if S[i][j] == '.':
            l += 1
        else:
            tmp.extend([l]*(j - begin))
            tmp.append(0)
            begin = j + 1
            l = 0
    if begin != W:
        tmp.extend([l]*(W - begin))
    HL.append(tmp)

WL = []
for i in range(W):
    l = 0
    begin = 0
    tmp = []
    for j in range(H):
        if S[j][i] == '.':
            l += 1
        else:
            tmp.extend([l]*(j - begin))
            tmp.append(0)
            begin = j + 1
            l = 0
    if begin != H:
        tmp.extend([l]*(H - begin))
    WL.append(tmp)

max_l = 0
for i in range(H):
    for j in range(W):
        l = HL[i][j] + WL[j][i]
        max_l = max(l, max_l)
print(max_l - 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np
import fractions
from functools import reduce

from copy import deepcopy


def gcd_list(nums):
    return reduce(fractions.gcd, nums)

def main():
    N = int(input())
    A = np.array(sorted(list(map(int, input().split()))))

    bools = np.ones(N, dtype=bool)

    gcd_val = 0
    ans = 0
    for i in range(N):
        A_cop = deepcopy(A)
        bl_cop = deepcopy(bools)

        fal = [i]
        bl_cop[fal] = False

        gcd_val = gcd_list(A_cop[bl_cop])

        if ans == 0 or ans < gcd_val:
            ans = gcd_val

    print(ans)

main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import fractions


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

    L_gcds = [0] * N
    L_gcd_tmp = L_gcds[0]
    for i in range(1, N):
        L_gcd_tmp = fractions.gcd(L_gcd_tmp, A[i-1])
        L_gcds[i] = L_gcd_tmp

    R_gcds = [0] * N
    R_gcd_tmp = R_gcds[0]
    for j in range(1, N):
        R_gcd_tmp = fractions.gcd(R_gcd_tmp, A[N-j])
        R_gcds[j] = R_gcd_tmp
    R_gcds.reverse()

    LR_gcds = [0] * N
    for k in range(0, N):
        LR_gcds[k] = fractions.gcd(L_gcds[k], R_gcds[k])

    print(max(LR_gcds))

main()
### BUGGY CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = []
for i in range(N):
  p = sum([i for i in range(1, ps[i]+1)])/ps[i]
  Es.append(p)
  if i<(K-1):
    continue
  elif i==(K-1):
    max_e = sum(Es)
  else:
    Es = Es[1:]
    if sum(Es)>max_e:
      max_e = sum(Es)
print(max_e)

### FIXED CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [(ps[i]+1)/2 for i in range(N)]
maxs = []
for i in range(1, N+1):
  if i<K:
    continue
  elif i==K:
    tmp = sum(Es[:i])
    maxs.append(tmp)
  else:
    tmp = tmp +Es[i-1]-Es[i-K-1]
    maxs.append(tmp)
print(max(maxs))
### BUGGY CODE ###

import sys
n = int(input())
a_ls = [bin(int(i))[2:].zfill(60) for i in sys.stdin.readline().split()]
MOD = 10**9 + 7
#memo_ls[i][j] : 後ろからi番目まででj桁に1がある個数
memo_ls = [[0 for j in range(60)] for i in range(n+1)]
for i, a in enumerate(a_ls[::-1], 1):
    for j, k in enumerate(a[::-1]):
        memo_ls[i][j] = memo_ls[i-1][j] + int(k)

res = 0
for i in range(60):
    res += memo_ls[-1][i] * (n - memo_ls[-1][i]) * 2 ** i
    res %= MOD
print(res)

### FIXED CODE ###

import sys
n = int(input())
a_ls = [bin(int(i))[2:].zfill(60)[::-1] for i in sys.stdin.readline().split()]
MOD = 10**9 + 7
#memo_ls[i][j] : 後ろからi番目まででj桁に1がある個数
memo_ls = [[0 for j in range(60)] for i in range(n+1)]
ct = {i : 0 for i in range(60)}
for i, a in enumerate(a_ls[::-1], 1):
    for j, k in enumerate(a):
        if k == "1":
            ct[j] += 1

res = 0
for i in range(60):
    res += ct[i] * (n - ct[i]) * 2 ** i
    res %= MOD
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
# import numpy as np


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

    count = 0
    for i in range(N):
        m = min(P[:i+1])
        # print(i+1, Q)
        if m == P[i]:
            count += 1
    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
# import numpy as np


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

    count = 0
    min_P = 200000
    for i in range(N):
        if min_P > P[i]:
            min_P = P[i]
        if min_P == P[i]:
            count += 1
    print(count)

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

s = input()
q = int(input())
is_reverse = 0
for i in range(q):
    query = input()
    if query[0] == '1':
        is_reverse = (is_reverse+1) % 2
    else:
        _, f, c = query.split()
        if (is_reverse+int(f))%2 == 0:
            s += c
        else:
            s = c + s
if is_reverse:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q = int(input())
is_reverse = 0
left = ''
for i in range(q):
    query = input()
    if query[0] == '1':
        is_reverse = (is_reverse+1) % 2
    else:
        _, f, c = query.split()
        if (is_reverse+int(f))%2 == 0:
            s += c
        else:
            left += c
s = left[::-1] + s
if is_reverse:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

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

dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    for j in range(0,W+1):
        if j<w:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j-w]+v,dp[i-1][j])
print(max(max(dp)))

### FIXED CODE ###

import numpy as np

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

dp=np.zeros([n+1,W+1],dtype=int)

for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v,dp[i-1][w:])
print(np.max(dp))