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

def main():
    n=int(input())
    g=[[]for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        g[a-1].append((b-1,i))
        g[b-1].append((a-1,i))

    def path(i,goal,mam=-1):
        if len(g[i][0])==1 and g[0]==mam:
            return 0
        else:
            for j,idx in g[i]:
                if j==mam:
                    continue
                if j==goal:
                    return 1<<idx
                p=path(j,goal,i)
                if p>0:
                    return p | (1<<idx)
            return 0

    m=int(input())
    ps=[]
    for _ in range(m):
        a,b=map(int,input().split())
        ps.append(path(a-1,b-1))

    import numpy as np
    dp=np.zeros(1<<m,dtype=np.int64)
    dp[0]=1
    for i in range(n-1):
        newdp=np.zeros(1<<m,dtype=np.int64)
        hit=0
        for j,p in enumerate(ps):
            a=p & (1<<i)
            if p & (1<<i):
                hit+=1<<j
        for j in range(1<<m):
            newdp[j|hit]+=dp[j]
        
        dp+=newdp
    print(dp[-1])
main()

### FIXED CODE ###

n=int(input())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append((b-1,i))
    g[b-1].append((a-1,i))

def path(i,goal,mam=-1):
    if len(g[i][0])==1 and g[0]==mam:
        return 0
    else:
        for j,idx in g[i]:
            if j==mam:
                continue
            if j==goal:
                return 1<<idx
            p=path(j,goal,i)
            if p>0:
                return p | (1<<idx)
        return 0

m=int(input())
ps=[]
for _ in range(m):
    a,b=map(int,input().split())
    ps.append(path(a-1,b-1))

dp=[0]*(1<<m)
dp[0]=1
for i in range(n-1):
    newdp=[0]*(1<<m)
    hit=0
    for j,p in enumerate(ps):
        a=p & (1<<i)
        if p & (1<<i):
            hit+=1<<j
    for j in range(1<<m):
        newdp[j|hit]+=dp[j]
    for j in range(1<<m):
        dp[j]+=newdp[j]
print(dp[-1])
### BUGGY CODE ###

Num , Sum =  map(int,input().split())
count = 0

for x in range(Num+1):
    for y in range (Num+1):
        for z in range (Num+1):
            if Sum == x + y + z :
                count += 1

print(count)

### FIXED CODE ###

Num , Sum =  map(int,input().split())
count = 0
check = 0

for x in range(Num+1):
    for y in range ( Num+1 ):

        if 0 <= (Sum - x ) - y <= Num :
            count += 1

print(count)
### BUGGY CODE ###

def writeanderase(n , a):

    ans = []

    for i in range(n):
        if ans.count(a[i]) == 0:
            ans.append(a[i])
        else:
            ans.remove(a[i])

    return len(ans)

def main():
    n = int(input())
    a = [int(input()) for i in range(n)]
    print(writeanderase(n , a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def writeanderase(n , a):

    ans = {}
    count = 0

    for i in range(n):
        if a[i] in ans:
            ans[a[i]] += 1
        else:
            ans[a[i]] = 1

    for i in ans.values():
        count += i % 2

    return count

def main():
    n = int(input())
    a = [int(input()) for i in range(n)]
    print(writeanderase(n , a))

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

def main():
    a,b = map(int,input().split())
    if a-b+1>=673:
        print(0)
    else:
        mini = 2020
        for i in range(a,b+1):
            for j in range(a,i):
                joke = i*j%2019
                if joke<mini:
                    mini = joke
        print(mini)
main()

### FIXED CODE ###

a,b=map(int,input().split())
x=0;md=0;min=4000
if a+2022<b:
    b=a+2022

for i in range(a,b,1):
    for j in range(a+1,b+1,1):
        x = i * j
        md = x % 2019
        if md < min:
            min = md


print(min)
### BUGGY CODE ###

n = int(input())

print(sum([i for i in range(1, n)]))


### FIXED CODE ###

n = int(input())

ans = n * (n // 2)
if (n - 1) % 2 == 0:
   print(ans)
else:
   print(ans - int(n / 2))
### BUGGY CODE ###

def prf(n):
    pf = {}
    for i in range(2, int(n ** 1 / 2) + 1):
        while n % i == 0:
            if not i in pf:
                pf[i] = 0
            pf[i] += 1
            n //= i
    if n > 1:
        pf[n] = 1
    return pf

def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result

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

ans = 1
for i in prf(m).values():
    ans = ans * comb(n - 1 + i, i) % mod
    
print(ans)

### FIXED CODE ###

#素因数分解
def prf(m):
    pf = {}
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf[i] = pf.get(i, 0)+1
            #get:辞書のkeyを指定し、そのkeyがあればvalueを返し、なければ指定した値を返す
            m //= i
    if m > 1:
        pf[m] = 1
        #mの平方根よりも大きい数が残る場合はその数自体が素因数(m=10=2*5)
    return pf

#組合せ（nCk）
def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result
 
n, m = map(int, input().split())
mod = 10 ** 9 + 7

ans = 1
for i in prf(m).values():
    ans = ans * comb(n - 1 + i, i) % mod
    #重複組合せ：N-1枚の仕切り（aとaの間の個数に相当）を使って、i（指数）を振り分ける場合の数
print(ans)
### BUGGY CODE ###

import sys,io
from functools import lru_cache
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
N,W=reads()
weight,value=[0]*N,[0]*N
for i in range(N):
    weight[i],value[i]=reads()
@lru_cache(None)
def dp(i,w):
  res=0
  if  i==0:
    return 0
  if w-weight[i-1]>=0:
    com=dp(i-1,w-weight[i-1])+value[i-1]
  else:
    com=0
  return max(dp(i-1,w),com)
print(dp(N,W))
#print("{}".format(dp(N,W)))

### FIXED CODE ###

# D問題とほぼ同じだが計算量が問題になる．
# 前回と違い重さの制約が，W<10^9なので，重さのノードを作ってしまうと，計算量がどう仕様もなくなる
# なので，価値に対してノードを作ってあげて，最小の重さを計算するようにする

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

W = []
V = []

for i in range(N):
    w,v = map(int,input().split())
    W.append(w)
    V.append(v)
# dp[v][i] := 商品iまで選択して，価値がv以下となった場合について，最小の重さ
import math
import numpy as np
dp = np.ones((10**3*(N+10))) * np.inf
dp[0] = 0
for v,w in zip(V,W):
    np.minimum(dp[:-v]+w, dp[v:],out=dp[v:])
print(np.where(dp<=W_max)[0][-1])
### BUGGY CODE ###

import bisect


N = int(input())

lis = []

A1 = int(input())


lis.append(A1)


for i in range(N-1):

    A = int(input())

    flag = True
    ins = bisect.bisect_left(lis,A)

    if ins == 0:
        B = [A] + lis
        lis = B.copy()

    if lis[ins-1] < A:
        lis[ins-1] = A

"""
    for l in lis:

 

        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break

    if flag:
        lis.append(A)
"""

#print (lis)
print (len(lis))


### FIXED CODE ###

import bisect

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print (len(seq)-1)
### BUGGY CODE ###

H,W = map(int, input().split())
field = []
countd = 0
for _ in range(H):
    ls = []
    st = str(input())
    for ss in st:
        ls.append(ss)
        if ss =='.':
            countd += 1
    field.append(ls)

from collections import deque

dis = [[float('inf')]*51 for i in range(51)]
que = deque([])
que.append([0,0,0])
dis[0][0] = 0
while len(que) > 0:
    pre = que.popleft()
    d = pre[0]
    x = pre[1]
    y = pre[2]
    for dx in [-1,1]:
        for dy in [-1,1]:
            if 0<=x+dx<=H-1:
                if field[x+dx][y]=='.':
                    dis[x+dx][y] = d+1
                    que.append([d+1,x+dx,y])
            if 0<=y+dy<=W-1:
                if field[x][y+dy]=='.':
                    dis[x][y+dy] = d+1
                    que.append([d+1,x,y+dy])

an = dis[H-1][W-1]
if an ==float('inf'):
    print(-1)
else:
    print(countd-an-1)


### FIXED CODE ###

H,W = map(int, input().split())
field = []
countd = 0
for _ in range(H):
    ls = []
    st = str(input())
    for ss in st:
        ls.append(ss)
        if ss =='.':
            countd += 1
    field.append(ls)
import heapq

def caldis(field):#ある点を黒にして計算できる距離の中で際異端のものを求める
    used = [[False]*50 for i in range(50)]
    dis = [[float('inf')]*51 for i in range(51)]
    dis[0][0] = 0
    que = []
    heapq.heappush(que,[0,0,0])
    while len(que)>0:
        pre = heapq.heappop(que)
        d = pre[0]
        px = pre[1]
        py = pre[2]
        if used[px][py] ==True:
            continue
        used[px][py] = True
        dis[px][py] = d
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=px+dx<=H-1:
                    if field[px+dx][py]=='.':
                        heapq.heappush(que,[d+1,px+dx,py])
                if 0<=py+dy<=W-1:
                    if field[px][py+dy]=='.':
                        heapq.heappush(que,[d+1,px,py+dy])
    res = dis[H-1][W-1]
    return res
an = caldis(field)
if an==float('inf'):
    print(-1)
else:
    print(countd-an-1)
### BUGGY CODE ###

A,B,K = map(int,input().split())
ans = []
for i in range(A,B+1):
    if i < A+K:
        if i in ans:
            pass
        else:
            ans.append(i)
    if i > B-K:
        if i in ans:
            pass
        else:
            ans.append(i)
for i in range(len(ans)):
    print(ans[i])

### FIXED CODE ###

A,B,K = map(int,input().split())
if A+K > B:
    for i in range(A,B+1):
        print(i)
else:
    for i in range(A,A+K):
        print(i)
    if A+K > B-K:
        for i in range(A+K,B+1):
            print(i)
    else:
        for i in range(B-K+1,B+1):
            print(i)
### BUGGY CODE ###

from collections import defaultdict
from itertools import product
import sys

input = sys.stdin.readline

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist


H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = defaultdict(list)
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.': E[(i, j)].append((x, y)); E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    for d in D.values():
        if d != INF:
            ans = max(d, ans)
print(ans)

### FIXED CODE ###

from collections import deque
from itertools import product

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))

def bfs(s):
    q = deque([(s, 0)])
    dist = {v: -1 for v in V}
    while q:
        v, d = q.popleft()
        if dist[v] >= 0: continue
        dist[v] = d
        for u in E[v]:
            if dist[u] < 0:
                q.append((u, d+1))
    return dist

ans = 0
for v in V:
    dist = bfs(v)
    ans = max(ans, max(dist.values()))
print(ans)
### BUGGY CODE ###

N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = sorted(list(map(int, input().split(" "))))
bottoms = sorted(list(map(int, input().split(" "))))


def binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] >= num:
        return binary_search(check_list, num, left, mid - 1)
    else:
        return binary_search(check_list, num, mid + 1, right)


total_count = 0
min_count = min(mids)
start_index = binary_search(bottoms, min_count, 0, N - 1)
for bottom in bottoms[start_index:]:
    mid_insert_index = binary_search(mids, bottom, 0, N - 1)
    for mid in mids[0:mid_insert_index]:
        total_count += binary_search(tops, mid, 0, N - 1)
print(total_count)


### FIXED CODE ###

import bisect
N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = list(map(int, input().split(" ")))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


# def left_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] >= num:
#         return left_binary_search(check_list, num, left, mid - 1)
#     else:
#         return left_binary_search(check_list, num, mid + 1, right)


# def right_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] > num:
#         return right_binary_search(check_list, num, left, mid - 1)
#     else:
#         return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    # bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    bottom_start_index = bisect.bisect_right(bottoms, mid)
    # top_end_index = left_binary_search(tops, mid, 0, N - 1)
    top_end_index = bisect.bisect_left(tops, mid)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)
### BUGGY CODE ###

m = int(input())
cnt = 0
res = None
for _ in range(m):
    d,c = map(int,input().split())
    while c:
        if c%2:
            if res is None:
                res = d
            else:
                res += d
                cnt += 1
                if res > 9:
                    res = res//10 + res%10
                    cnt += 1 
        d *= 2
        c //= 2
        cnt += c
        if d > 9:
            d = d//10 + d%10
            cnt += c
print(cnt)

### FIXED CODE ###

m = int(input())
cnt = 0
res = None
for _ in range(m):
    d,c = map(int,input().split())
    while c:
        if c%2:
            if res is None:
                res = d
            else:
                res += d
                cnt += 1
                if res > 9:
                    res = res//10 + res%10
                    cnt += 1 
        d *= 2
        c //= 2
        cnt += c
        if d > 9:
            d = d//10 + d%10
            cnt += c
print(cnt)
### BUGGY CODE ###

A,B=map(int,input().split())
lst=set()
i=2
while i<=A or i<=B:
    #print(i,A,B,lst)
    if A%i==0 and B%i==0:
        flag=1
        for l in lst:
            if i%l==0:
                flag=0
                break

        if flag:
            lst.add(i)
        while A%i==0:
            A=A//i
        while B%i==0:
            B=B//i
    i+=1


lst.add(1)
#print(lst)
print(len(lst))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
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

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

N = int(input())

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

ones = [0] * 60
m = 10 ** 9 + 7

for Ai in A:
    for digit in range(len(bin(Ai)) - 2):
        ones[digit] += ((Ai >> digit) & 1)

res = 0
for i, num in enumerate(ones):
    res += (1 << i) * num * (N - num)

print(res % m)


### FIXED CODE ###

N = int(input())

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

num = [[0, 0] for _ in range(60)]

for Ai in A:
    for digit in range(60):
        if (Ai >> digit) & 1:
            num[digit][1] += 1
        else:
            num[digit][0] += 1

res = 0
for i, p in enumerate(num):
    res += (1 << i) * p[0] * p[1]

m = 10 ** 9 + 7
print(res % m)
### BUGGY CODE ###

s = input()

target = 2019

memo = [0]*200000

counts = []
countOfMod = {}
# i = 0
# while s >= 10:
#     mod = s % target
#     s = int(s / 10)
#     countOfMod[mod] = countOfMod.get(mod, 0) + 1

length = len(s)
for i in range(0, length+1):
    value = int(s[-i:]) if i > 0 else 0
    mod = value % target
    countOfMod[mod] = countOfMod.get(mod, 0) + 1

results = [int(m*(m-1)/2) for m in countOfMod.values() if m > 1]


print(sum(results))
# print(count)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

# 出現した数のフラグを立てればよいだけでは
import sys
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
# A = list(map(int, read().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0
for i in range(N):
    if count[A[i]] >= 2:
        ans += 1
        happend.add(A[i])
        continue
    for j in range(1, int(A[i]**(1/2))+2):
        if A[i] % j == 0:
            if j in happend or A[i]//j in happend:
                ans += 1
                break
    happend.add(A[i])
print(N-ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  # 0~max(A)の数についてのリスト
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            # aが存在したという証拠だけは残しておく
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)
### BUGGY CODE ###

import itertools
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.readline())


@lru_cache(maxsize=None)
# @debug
def is_ok(s):
    if len(s) == 0:
        return True
    if len(s) == 2:
        return s not in ['AB', 'BA']
    for i in range(len(s) - 2):
        if s[i:i + 2] not in ['AB', 'BA'] and is_ok(s[:i] + s[i + 2:]):
            return True
    return False


def test(N):
    ret = 0
    for s in itertools.product('ABC', repeat=N):
        s = ''.join(s)
        ret += is_ok(s)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


# print(test(N))
# N = 10 ** 7

# 解説AC
# 偶数番目のAとBを反転して、AAとBB以外を取り除く
# AまたはBが半分より多いときダメなので全体から引く
ans = pow(3, N, MOD)

invs = mod_invs(max=N, mod=MOD)
ncr = 1  # NCr
p2r = 1  # pow(2, N - r, MOD)
for r in range(N, N // 2, -1):
    # ans -= comb.ncr(N, r) * pow(2, N - r, MOD) * 2 % MOD
    ans -= ncr * p2r * 2 % MOD
    ans %= MOD
    ncr *= r * invs[N - r + 1]
    ncr %= MOD
    p2r *= 2
    p2r %= MOD
print(ans)


### FIXED CODE ###

import itertools
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.readline())


@lru_cache(maxsize=None)
# @debug
def is_ok(s):
    if len(s) == 0:
        return True
    if len(s) == 2:
        return s not in ['AB', 'BA']
    for i in range(len(s) - 2):
        if s[i:i + 2] not in ['AB', 'BA'] and is_ok(s[:i] + s[i + 2:]):
            return True
    return False


def test(N):
    ret = 0
    for s in itertools.product('ABC', repeat=N):
        s = ''.join(s)
        ret += is_ok(s)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


# print(test(N))
# N = 10 ** 7

# 解説AC
# 偶数番目のAとBを反転して、AAとBB以外を取り除く
# AまたはBが半分より多いときダメなので全体から引く
ans = pow(3, N, MOD)

invs = mod_invs(max=N, mod=MOD)
ncr = 1  # NCr
p2r = 1  # pow(2, N - r, MOD)
for r in range(N, N // 2, -1):
    # ans -= comb.ncr(N, r) * pow(2, N - r, MOD) * 2 % MOD
    ans -= ncr * p2r * 2 % MOD
    ans %= MOD
    ncr *= r * invs[N - r + 1]
    ncr %= MOD
    p2r *= 2
    p2r %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())

ans = 1

for e in [*map(int, input().split())]:
    ans *= e

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


### FIXED CODE ###

n = int(input())

a = [*map(int, input().split())]
for e in a:
    if e == 0:
        print(0)
        exit(0)

ans = 1
for e in a:
    ans *= e
    if ans > 10**18:
        print(-1)
        exit(0)

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

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
for i in range(61):
  n = sum([int(bin(a>>i)[-1]) for a in A])
  ans += (n * (N - n) * pow(2, i) % MOD)
print(ans%MOD)

### FIXED CODE ###

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

N,K=map(int,input().split())
td=[[int(a) for a in input().split()]for i in range(N)]

td=sorted(td,key=lambda x:-x[1])

ans=0
eat=[]
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.append(t)
  else:
    noteat.append(d)
temp_result=ans+len(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.append(t)
    max_result=max(max_result,temp_result)
print(max_result)
 

### FIXED CODE ###

N,K=map(int,input().split())
td=[[int(a) for a in input().split()]for i in range(N)]

td=sorted(td,key=lambda x:-x[1])

ans=0
eat=set([])
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.add(t)
  else:
    noteat.append(d)
temp_result=ans+len(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.add(t)
    max_result=max(max_result,temp_result)
print(max_result)
### BUGGY CODE ###

from collections import Counter
N,C = map(int,input().split())
link =[[] for _ in range(C+1)]
for i in range(N):
    x,y,c=[int(i) for i in input().split()]
    link[c].append((x,y))
siyou = [[] for _ in range(C+1)]
for i in range(1,C+1):
  for x,y in link[i]:
    x -= 0.5
    while x < y:
      if x in siyou[i]:
        x += 0.5
        continue
      siyou[i].append(x)
      x += 0.5
from itertools import chain
flat = list(chain.from_iterable(siyou))
ans = Counter(flat).most_common(1)
print(ans[0][1])

### FIXED CODE ###

import numpy as np
from collections import Counter
N,C = map(int,input().split())
link =[[] for _ in range(C+1)]
for i in range(N):
    x,y,c=[int(i) for i in input().split()]
    link[c].append((x,y))
siyou = np.array([0] * (C) * 100000).reshape(C,100000)
for i in range(1,C+1):
  for x,y in link[i]:
    siyou[i-1][x-1:y] = 1
print(np.max((np.sum(siyou, axis=0))))