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

import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
        if np.count_nonzero(a==i) >1:
            dp[i] = False
    print(np.count_nonzero(dp[a] == True))

### FIXED CODE ###

import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in a:
        for j in np.arange(i, max_num, i):
            dp[j] += 1
    print(np.count_nonzero(dp[a] == 1))
### BUGGY CODE ###

H, N, *AB = map(int, open(0).read().split())
A = AB[::2]
B = AB[1::2]

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])


### FIXED CODE ###

H, N, *AB = map(int, open(0).read().split())
A = []
B = []
for a, b in zip(*[iter(AB)] * 2):
    A.append(a)
    B.append(b)

dp = [float("inf")] * (H + 1)
dp[0] = 0

for i in range(N):
    for h in range(H):
        dec_health = min(h + A[i], H)
        dp[dec_health] = min(dp[dec_health], dp[h] + B[i])
print(dp[-1])
### BUGGY CODE ###

def binary_search(list,target):

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = int((left + right)/2)
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return result
	else:
		return result


if __name__=="__main__":
    n=int(input())
    s=list(input())
    rlist=[]
    glist=[]
    blist=[]
    ans=0
    if len(s)<=3:
        print(0)
        exit()
    for i in range(n):
        if s[i]=="R":
            rlist.append(i)
        elif s[i]=="G":
            glist.append(i)
        else:
            blist.append(i)
    if len(rlist)==0 or len(glist)==0 or len(blist)==0:
        print(0)
        exit()
    ans+=len(rlist)*len(glist)*len(blist)
    for i in glist:
        for j in blist:
            if i>j :
                if binary_search(rlist,2*i-j)!=-1:
                    ans-=1
                if binary_search(rlist,2*j-i)!=-1:
                    ans-=1
                if (i+j)/2 in rlist:
                    ans-=1
            else:
                if binary_search(rlist,2*i-j)!=-1:
                    ans-=1
                if binary_search(rlist,2*j-i)!=-1:
                    ans-=1
                if (i+j)/2 in rlist:
                    ans-=1

    print(ans)

### FIXED CODE ###

def binary_search(list,target):

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = int((left + right)/2)
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return result
	else:
		return result


if __name__=="__main__":
    n=int(input())
    s=list(input())
    rlist=[]
    glist=[]
    blist=[]
    ans=0
    if len(s)<=3:
        print(0)
        exit()
    for i in range(n):
        if s[i]=="R":
            rlist.append(i)
        elif s[i]=="G":
            glist.append(i)
        else:
            blist.append(i)
    if len(rlist)==0 or len(glist)==0 or len(blist)==0:
        print(0)
        exit()
    ans+=len(rlist)*len(glist)*len(blist)
    for i in range(n-2):
        for j in range(i+1,n-1):
            k=2*j-i
            if s[i]==s[j]:
                continue
            elif k>len(s)-1:
                continue
            else:
                if s[k]!=s[i] and s[k]!=s[j]:
                    ans-=1

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

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    ab[a-1][b-1] = 1
    ab[b-1][a-1] = 1

ans = 0
for i in range(n):
    flag = True
    for j in range(n):
        if ab[i][j] == 1:
            if h[j] >= h[i]:
                flag = False
                break
    if flag:
        ans += 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
ab = [True] * n
for _ in range(m):
    a, b = map(int, input().split())
    if h[a-1] > h[b-1]:
        ab[b-1] = False
    elif h[b-1] > h[a-1]:
        ab[a-1] = False
    else:
        ab[a-1] = False
        ab[b-1] = False

print(ab.count(True))
### BUGGY CODE ###

import numpy as np
import sys

input=sys.stdin.readline

n,m,q = list(map(int, input().split()))

lrs = [list(map(int, input().split())) for _ in range(m)]
pqs = [list(map(int, input().split())) for _ in range(q)]

train_array = np.zeros((n+1,n+1),dtype=int)

for lr in lrs:
    train_array[lr[0]][lr[1]] +=1


#print(train_array)

train_array_ruisekiwa = np.zeros((n+1,n+1), dtype = int)

for index, train_vector in enumerate(train_array):
    train_array_ruisekiwa[index][0] = train_vector[0]

    for i in range(1, n+1):
        train_array_ruisekiwa[index][i] = train_array_ruisekiwa[index][i-1] + train_vector[i]

#print(train_array_ruisekiwa)

for pq in pqs:
    ans = 0
    for i in range(pq[0],pq[1]+1):
        ans += train_array_ruisekiwa[i][pq[1]] - train_array_ruisekiwa[i][pq[0] - 1]

    print(ans)

### FIXED CODE ###

import numpy as np
import sys

input=sys.stdin.readline

n,m,q = list(map(int, input().split()))

lrs = [list(map(int, input().split())) for _ in range(m)]
pqs = [list(map(int, input().split())) for _ in range(q)]

train_array = np.zeros((n+1,n+1),dtype=int)

for lr in lrs:
    train_array[lr[0]][lr[1]] +=1


#print(train_array)

train_array_ruisekiwa = np.zeros((n+1,n+1), dtype = int)

for i in range(1, n+1):
    for j in range(1, n+1):
        train_array_ruisekiwa[i][j] = train_array[i][j] + train_array_ruisekiwa[i][j-1] + train_array_ruisekiwa[i-1][j] - train_array_ruisekiwa[i-1][j-1]

#print(train_array_ruisekiwa)

for pq in pqs:
    print(train_array_ruisekiwa[pq[1]][pq[1]] - train_array_ruisekiwa[pq[1]][pq[0]-1] - train_array_ruisekiwa[pq[0]-1][pq[1]] + train_array_ruisekiwa[pq[0]-1][pq[0]-1])
### BUGGY CODE ###

from math import trunc, sqrt

def p(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x

def perm(x,y,z):
    if x==y and y==z and z==x:
        return 1
    if x!=y and y!=z and z!=x:
        return 6
    return 3

def f(n):
    mn=trunc(sqrt(n//3)+1)
    k=0
    for x in range(1,mn+1):
        for y in range(x,mn+1):
            for z in range(y,mn+1):
                if p(x,y,z)==n:
                    k += perm(x,y,z)
    return k

N=int(input())

for n in range(1,N+1):
    print(f(n))
    


### FIXED CODE ###

N=int(input())

a=[0]*N

x=1
while x*x<=N:
    y=1
    while x*x+y*y+x*y<=N:
        z=1
        while z*z+x*x+y*y+x*y+z*y+z*x<=N:
            a[z*z+x*x+y*y+x*y+z*y+z*x-1]+=1
            z+=1
        y+=1
    x+=1

for n in a:
    print(n)
### BUGGY CODE ###

H,W=map(int,input().split())
hlen= list(map(int,input().split()))
wlen =	list(map(int,input().split()))
def is_unique(l):
    return len(l) == len(set(l))
if not is_unique(hlen) or not is_unique(wlen):
	print(0)
	exit()
def Count(x,l):
	ret = 0
	while l[ret] > x :
		ret += 1
		if ret == len(l):
			break
	return ret	
hlen.sort(reverse=True)
wlen.sort(reverse=True)

m = max(hlen[0],wlen[0])
count = 1
for num in range(1,H*W+1)[::-1]:
	flagh = 0
	flagw = 0
	if num in hlen:
		flagh = 1
	if num in wlen:
		flagw = 1
	if flagh and flagw:
		count *= 1
	elif flagh:
		count *= Count(num,wlen)
	elif flagw:
		count *= Count(num,hlen)
	else:
		count *= Count(num,hlen)*Count(num,wlen) - (m-num)
	#print(num,flagh,flagw,count)
print(count % (10**9+7))

### FIXED CODE ###

H,W=map(int,input().split())
hlen = list(map(int,input().split()))
wlen =	list(map(int,input().split()))
hlen.sort(reverse=True)
wlen.sort(reverse=True)
hlen.append(0)
wlen.append(0)

m = H*W
count = 1
h=0
w=0
for num in range(1,H*W+1)[::-1]:
	if hlen[h] == num and wlen[w] == num:
		count *= 1
		h += 1
		w += 1
	elif hlen[h] == num:
		count *= w
		h += 1
	elif wlen[w] == num:
		count *= h
		w += 1
	else:
		count *= h*w - (m-num)
	#print(num,flagh,flagw,count)
	count %= (10**9+7)
print(count)
### BUGGY CODE ###


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

sum = 0
A.sort(reverse=False)

for i in range(N):
    for j in range(N-(i+1)):
        sum += A[i]*A[j+i+1]

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

### FIXED CODE ###


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


mod = 10**9+7
s = sum(A)

ans = 0

for i in range(n):
    s -= A[i]
    ans += (A[i] * s) % mod

print(ans%mod)
### BUGGY CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost+1):
                continue
            costgrid[nx][ny]=min(costgrid[nx][ny],cost+1)
            heapq.heappush(q,(cost+1,nx,ny))
            if nx==gx and ny==gy:
                ans=min(costgrid[nx][ny],ans)
                q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)



### FIXED CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost):
                break
            if(costgrid[nx][ny]>cost+1):
                costgrid[nx][ny]=cost+1
                heapq.heappush(q,(cost+1,nx,ny))
                if nx==gx and ny==gy:
                    ans=min(costgrid[nx][ny],ans)
                    q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

MOD = int(1e9 + 7)

s = input()
digits = len(s)

cnt = 0
for i, c in enumerate(reversed(s)):
    if c == '?':
        continue
    n = int(c) * pow(10, i, 13) % 13
    cnt += n
# print(cnt)

before = [0] * 13
first_time = True
for i, c in enumerate(reversed(s)):
    if c != '?':
        continue
    if first_time:
        for j in range(10):
            n = j * pow(10, i, 13) % 13
            before[n] += 1
        first_time = False
        continue
    current = [0] * 13
    for j in range(10):
        n = j * pow(10, i, 13) % 13
        current[n] += 1
    after = [0] * 13
    for j in range(13):
        for k in range(13):
            after[j] += before[k] * current[(13 - k + j) % 13]
        after[j] %= MOD
    before = after

if first_time:
    if cnt % 13 == 5:
        print(1)
    else:
        print(0)
else:
    print(before[(5 - (cnt % 13)) % 13])


### FIXED CODE ###

MOD = int(1e9 + 7)

s = input()
digits = len(s)

cnt = 0
for i, c in enumerate(reversed(s)):
    if c == '?':
        continue
    n = int(c) * pow(10, i, 13) % 13
    cnt += n
# print(cnt)

before = [0] * 13
first_time = True
for i, c in enumerate(reversed(s)):
    if c != '?':
        continue
    if first_time:
        for j in range(10):
            n = j * pow(10, i, 13) % 13
            before[n] += 1
        first_time = False
        continue
    current = [0] * 13
    for j in range(10):
        n = j * pow(10, i, 13) % 13
        current[n] += 1
    after = [0] * 13
    for j in range(13):
        for k in range(13):
            after[j] += before[k] * current[(13 - k + j) % 13]
        after[j] %= MOD
    before = after

if first_time:
    if cnt % 13 == 5:
        print(1)
    else:
        print(0)
else:
    print(before[(5 - (cnt % 13)) % 13])
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int,input().split())))

#%%

# print(n, m, ab)
# n, m, ab = 4, 30, [[6, 18], [2, 5], [3, 10], [7, 9]]


#%%
ab.sort()

#%%
ans = 0
num = 0
while num < m:
    a0 = ab[0][0]
    b0 = ab[0][1]
    if b0 >= m - num:
        ans += a0 * (m - num)
        break
    else:
        ans += a0 * b0
        num += b0
        ab.remove([a0, b0])
#%%
print(ans)
#%%


### FIXED CODE ###

n, m = map(int, input().split())
ab = []
prod = [0]
prod_cum = [0]

num_cum = [0]
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a,b])


#%%
ab.sort()

for i in range(n):
    a, b = ab[i][0],ab[i][1]
    # prod.append(a*b)
    prod_cum.append(a*b + prod_cum[-1])
    num_cum.append(b + num_cum[-1])
ab = [[0,0]] + ab
# print(ab)
# print(prod)
# print(prod_cum)
# print(num_cum)
# print(n, m, ab)
# n, m, ab = 4, 30, [[6, 18], [2, 5], [3, 10], [7, 9]]


#%%
ans = 0
prod = 0
for i in range(0, n+1):
    if num_cum[i] >= m:
        print(prod_cum[i] - ab[i][0] * (num_cum[i]-m))
        break



#%%
# ans = 0
# num = 0
# while num < m:
#     a0 = ab[0][0]
#     b0 = ab[0][1]
#     if b0 >= m - num:
#         ans += a0 * (m - num)
#         break
#     else:
#         ans += a0 * b0
#         num += b0
#         ab.remove([a0, b0])
#%%
# print(ans)
#%%
### BUGGY CODE ###

def resolve():
    import math

    def primes(n):
        ass = []
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        for i in range(len(is_prime)):
            if is_prime[i]:
                ass.append(i)
        return ass

    def divisor(n):
        ass = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                if i != 1:
                    ass.append(i)
                if i ** 2 == n:
                    continue
                ass.append(n // i)
        return ass

    n = int(input())
    a = list(map(int, input().split()))
    a = list(set(a))
    pair = False
    divisors = set(divisor(a[0]))
    ggcd = a[0]
    for i in range(1, len(a)):
        divs = set(divisor(a[i]))
        if len(divs & divisors) != 0:
            pair = True
            break
        else:
            divisors = divisors | divs
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break
    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()

### FIXED CODE ###

def resolve():
    import math
    n = int(input())
    a = list(set(map(int, input().split())))
    maxa = max(a)

    ggcd = a[0]
    for i in range(1, len(a)):
        ggcd = math.gcd(ggcd, a[i])
        if ggcd == 1:
            break

    pair = False

    c = [0] * (10**6+ 1)
    for i in a:
        c[i] += 1

    for i in range(2, maxa+1):
        cnt = 0
        for j in range(i, maxa+1, i):

            cnt += c[j]
        if cnt > 1:
            pair = True

    if ggcd != 1:
        print("not coprime")
    else:
        if pair:
            print("setwise coprime")
        else:
            print("pairwise coprime")
resolve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = [0] * (A[-1] + 1)
    ans = 0
    for a in A:
        for i in range(1, int(a ** 0.5) + 1):
            if a % i: continue
            if memo[i] or memo[a//i]:
                break
        else:
            ans += cost[a]

        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def solve():
    N = II()
    A = LI()

    mx = max(A)

    memo = [0] * (mx + 1)
    for a in A:
        for i in range(a, mx+1, a):
            memo[i] += 1
    # print(memo)

    ans = 0
    for a in A:
        if memo[a] == 1:
            ans += 1
    print(ans)

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



# -*- coding: utf-8 -*-
"""
Created on Thu Jan 31 03:17:55 2019

@author: rubug
"""

# -*- coding: utf-8 -*-
# 整数の入力
import numpy as np

N,Q = map(int,input().split())
s = str(input())
S = []
for c in s:
    S.append(c)

for i in range(Q):
    l, r = map(int, input().split())
    lst = S[int(l-1):int(r)]
    count = 0
    for i in range(len(lst)-1):
        if (lst[i] == "A")and(lst[i+1] == "C"):
            count += 1
    print(count)
            
        
    
    
    





### FIXED CODE ###





import numpy as np

N,Q = map(int,input().split())
S = []
for c in str(input()):
    S.append(c)

a = np.zeros(N)
   
for i in range(1,N):
    if (S[i-1] == "A")and(S[i] == "C"):
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
        
for i in range(Q):
    l, r = map(int, input().split())
    print(int(a[r-1] - a[l-1]))
### BUGGY CODE ###

import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

K = 1000000007
N = int(input())
A = [int(a) for a in input().split()]
li = [0] * 60
for n in range(N):
    for i in range(60):
        li[i] += A[n] >> i & 1
ans = 0
for i in range(60):
    ans += (1 << i) * li[i] * (N - li[i])
    ans %= K
print(ans)

### FIXED CODE ###

K = 1000000007
N = int(input())
A = [int(a) for a in input().split()]
li = [0] * 60
for n in range(N):
    li = [li[i] + (A[n] >> i & 1) for i in range(60)]
ans = 0
for i in range(60):
    ans += (1 << i) * li[i] * (N - li[i])
    ans %= K
print(ans)
### BUGGY CODE ###

A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in reversed(A):
    S += int(n)*d
    S %= 2019
    lis[S] += 1
    d *= 10

result = 0

for n in lis:
    result += (n*(n-1)//2)


print(result)


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
def ryuka(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1

    return ryuka(n-1) + ryuka(n-2)
print(ryuka(n))

### FIXED CODE ###

n = int(input())
li = [2,1]
for i in range(n+1):
    if i == 0:
        continue
    elif i == 1:
        continue
    else:
        li.append(li[i-2] + li[i-1])
print(li[n])
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [0 for i in range(W+1)]

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(max(dp))


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()