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

# D - Knapsack Queries on a tree

import bisect

n = int(input())

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

max_l = 10 ** 5

# dp table (for some amount)
dp = [None] * min(n, 2 ** 14)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2
    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

dpkeys = [[ww for ww, vv in dp[u]] for u in range(len(dp))]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dpkeys[u], l) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(input())
for i in range(q):
    u, l = map(int, input().split())
    print(solve(u - 1, l))


### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

q=int(input())
import math
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
for i in range(q):
    l,r=map(int,input().split())
    s=l
    count=0
    while s<=r:
        if is_prime((s+1)//2)==True:
            if is_prime(s)==True:
                count+=1
        s+=2
    print(count)

### FIXED CODE ###

q=int(input())
import math
import numpy as np
def is_prime(n):
    if n==1:return False
    for k in range(2,int(math.sqrt(n))+1):
        if n%k==0:
            return False
    return True
def is_is_prime(n):
    an=0
    if is_prime((n+1)//2)==True:
        if is_prime(n)==True:
            an=1
    return an
ko=[]
for i in range(1,10**5,2):
    ko.append(is_is_prime(i))

koko=np.cumsum(ko)

for i in range(q):
    l,r=map(int,input().split()) 
    if l==1:
        ans=koko[(r-1)//2]-koko[(l-1)//2]
    else:
        ans=koko[((r-1)//2)]-koko[((l-1)//2)-1]
    print(ans)
### BUGGY CODE ###

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[set([]) for ww in range(w)] for hh in range(h)]
dp[0][0] = {ab0, -ab0}
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            for ci in dp[ch][cw]:
                dp[ch+1][cw].add(ci + ab[ch+1][cw])
                dp[ch+1][cw].add(ci - ab[ch+1][cw])
        if cw < w-1:
            for ci in dp[ch][cw]:
                dp[ch][cw+1].add(ci + ab[ch][cw+1])
                dp[ch][cw+1].add(ci - ab[ch][cw+1])

for i in range(1 + size//2):
    for j in [1, -1]:
        if i*j in dp[h-1][w-1]:
            print(i)
            exit()


### FIXED CODE ###

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

ab = [[0]*w for i in range(h)]
for ch in range(h):
    for cw in range(w):
        ab[ch][cw] = abs(a[ch][cw] - b[ch][cw])

ab0 = ab[0][0]
size = 80*(h+w)
dp = [[0]*w for hh in range(h)]
dp[0][0] |= 2**(size + ab0)
dp[0][0] |= 2**(size - ab0)
for ch in range(h):
    for cw in range(w):
        if ch < h-1:
            dp[ch+1][cw] |= dp[ch][cw] << ab[ch+1][cw]
            dp[ch+1][cw] |= dp[ch][cw] >> ab[ch+1][cw]
        if cw < w-1:
            dp[ch][cw+1] |= dp[ch][cw] << ab[ch][cw+1]
            dp[ch][cw+1] |= dp[ch][cw] >> ab[ch][cw+1]

a = dp[h-1][w-1]>>size
m = a&(-a)
print(m.bit_length()-1)
### BUGGY CODE ###

##解答を見た
import sys
def input(): return sys.stdin.readline().strip()

H,W,D = map(int,input().split())
A = []
for i in range(H):
    tmp = list(map(int,input().split()))
    A.append(tmp)

pos = []
for k in range(1,H*W+1):
    for i in range(H):
        for j in range(W):
            if A[i][j] == k:
                pos.append([i+1,j+1])
                break
dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i-1][0]-pos[i-D-1][0])+abs(pos[i-1][1]-pos[i-D-1][1]))

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):##O(Q)
    print(dist[LR[i][1]-1]-dist[LR[i][0]-1])

### FIXED CODE ###

##解答を見た 手前でO(H^2W^2) ~O(10^9)くらいのことをしていた
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int,input().split())))

pos = [[0 for i in range(2)] for j in range(H*W+1)]

for i in range(H):
    for j in range(W):
        pos[A[i][j]][0] = i+1
        pos[A[i][j]][1] = j+1

dist = []
for i in range(1,H*W+1):##O(HW)
    if i<=D:
        dist.append(0)
    else:
        dist.append(dist[i-D-1]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1]))

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):
    print(dist[LR[i][1]-1]-dist[LR[i][0]-1])
### BUGGY CODE ###

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

for i in range(1, N+1):
    print(A.count(i))

### FIXED CODE ###

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

import collections
c = collections.Counter(A)

for i in range(1, N+1):
    print(c[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    mod = 10**9+7
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        m = 10**n
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*m) % 13] += dp[n][j] % mod
    print(dp[N][5] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        else:
            k = int(c)
            for j in range(13):
                dp[n+1][(j + k*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


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

import sys
sys.setrecursionlimit(400000000)
n,k=map(int,input().split())
h=list(map(int,input().split()))
flog=[-1]*n
#初期値は0
def Num(dest):
    if flog[dest-1]!=-1:
        return flog[dest-1]
    if dest<k+2:
        res=abs(h[dest-1]-h[0])
        flog[dest-1]=res
        return res
    else:
        min=float("inf")
        for i in range(1,k+1):
            tmp=Num(dest-i)+abs(h[dest-1]-h[dest-i-1])
            if min>tmp:
                min=tmp
        flog[dest-1]=min
        return min   
print(Num(n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ls = []
    t = n
    for i in range(2, int(n ** 0.5) + 1):
        while True:
            if t % i == 0:
                ls.append(i)
                t //= i
            else:
                break
    if t != 1:
        ls.append(t)
    mt = 10 ** 20
    for i in range(len(ls)):
        for v in itertools.combinations(ls, i):
            t = 1
            for vv in v:
                t *= vv
            mt = min(mt, (t - 1) + (n // t - 1))
    print(mt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    t = n
    mt = 10 ** 20
    for i in range(1, int(n ** 0.5) + 1):
        if t % i == 0:
            mt = min(mt, (i - 1) + (t // i - 1))
    print(mt)


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

import numpy as np
n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
point_list  = np.array([k] * n)

for i in a:
    point_list -= 1
    point_list[i-1] += 1

for i in point_list:
    if i >0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
point_list  = [k-q] * n 
for i in a:
    point_list[i-1] += 1
for i in point_list:
    if i >0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
  for j in range(n):
    a=ss[i:i+n,j:j+n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)
### BUGGY CODE ###

S = list(str(input()))
n = len(S)

S.reverse()

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+int(S[i])*10**i
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+int(S[i])*10**i
    cum2[i+1] = temp%3
#print(cum2)

d1 = {}
d2 = {}
ans = 0
for i in range(n+1):
    if cum1[i] in d1 and cum2[i] in d2:
        temp = d1[cum1[i]] & d2[cum2[i]]
        ans += len(temp)
    if cum1[i] not in d1:
        d1[cum1[i]] = {i}
    else:
        d1[cum1[i]].add(i)
    if cum2[i] not in d2:
        d2[cum2[i]] = {i}
    else:
        d2[cum2[i]].add(i)
print(ans)


### FIXED CODE ###

S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)
### BUGGY CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s_sub = []
    sorted_s = []
        
    for i in range(N):
        sorted_si = sorted(s[i])
        sorted_s_sub.append(''.join(sorted_si))

    sorted_s = sorted(sorted_s_sub)

    i = 0
    item_count = []
    while i < N:
        item = sorted_s[i]
        count = sorted_s.count(item)
        item_count.append(count)
        i += count  # count だけ進める
    
    for count in item_count:
        
        anagram_num += int(count * (count - 1) / 2)

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))


### FIXED CODE ###


def green_bin(s, N):
    anagram_num = 0
    sorted_s_sub = []
    sorted_s = []
        
    for i in range(N):
        sorted_si = sorted(s[i])
        sorted_s_sub.append(''.join(sorted_si))

    sorted_s = sorted(sorted_s_sub)

    i = 0
    item_count = []
    while i < N:
        item = sorted_s[i]
        j = i + 1
        count = 1
        while j < N:
            if item == sorted_s[j]:
                count += 1
                j += 1
            else:
                break
        item_count.append(count)
        i += count  # count だけ進める
    
    for count in item_count:
        
        anagram_num += int(count * (count - 1) / 2)

    return anagram_num


if __name__ == '__main__':
    N = int(input())
    s = []
    for n in range(N):
        sn = input()
        s.append(sn)
    print(green_bin(s, N))
### BUGGY CODE ###

import math
n,m,k=map(int,input().split())
mod=10**9+7
s=math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2))
cnt=0
s%=mod
for d in range(1,n):
        cnt+=d*(n-d)*m*m*s
        cnt%=mod
for d in range(1,m):
        cnt+=d*(m-d)*n*n*s
        cnt%=mod
print(cnt)

### FIXED CODE ###

import math
n,m,k=map(int,input().split())
mod=10**9+7
s=math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2))
cnt=0
s%=mod
a=(m*m*s)%mod
for d in range(1,n):
        cnt+=d*(n-d)*a
        cnt%=mod
a=(n*n*s)%mod
for d in range(1,m):
        cnt+=d*(m-d)*a
        cnt%=mod
print(cnt)
### BUGGY CODE ###

from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())
way = []
for rr in range(q):
    way.append(list(map(int, input().split())))
ans = 0


def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return sum(time[st-1+d: en: d])

for pr, ne in way:
    print(ask(pr, ne))

### FIXED CODE ###

from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = time[l] + (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return time[en-1] - time[st-1]


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))
### BUGGY CODE ###

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

if sum(B) > sum(A):
    print(-1)
else:
    diff = [a-b for a,b in zip(A,B)]
    plus = []
    minus = []
    equal = []
    for d in diff:
        if d >= 0:
            plus.append(d)
        elif d < 0:
            minus.append(d)
    lack = sum(minus)
    while lack < 0:
        lack += max(plus)
        plus.remove(max(plus))
    print(N-len(plus))

### FIXED CODE ###

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

if sum(B) > sum(A):
    print(-1)
else:
    diff = [a-b for a,b in zip(A,B)]
    plus = []
    minus_num = 0
    lack = 0
    for d in diff:
        if d >= 0:
            plus.append(d)
        elif d < 0:
            minus_num += 1
            lack += d
    plus.sort(reverse=True)
    i = 0
    while lack < 0:
        lack += plus[i]
        i += 1
        
    print(N-len(plus)+i)
### BUGGY CODE ###

import re

s = str(input())
find_s = 'ABC'
count = 0
while True:
    s_n = re.sub(r"{}".format(find_s), "BCA", s)
    n_find = re.findall(r"{}".format(find_s), s)
    count += len(n_find)

    if s_n.find(find_s) == -1:
        print(count)
        break
    else:
        s = s_n

### FIXED CODE ###

import re

s = input()
s = s.replace('BC', 'D')

count = 0
count_a = 0
for string in s:
    if string == 'A':
        count_a += 1
    elif string == 'D':
        count += count_a
    else:
        count_a = 0

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

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

while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]=a[i]//2
      ans+=1
      break
  else:
    break

print(ans)

### FIXED CODE ###

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

while True:
  flag=0
  for i in range(N):
    if a[i]%2==0:
      a[i]=a[i]//2
      ans+=1
      flag=1
  else:
      if flag==0:
          break

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

n=int(input())
l=sorted(list(map(int,input().split())))
bitlist=[]
num=l[-1]
b1=[]
while num!=0:
  b1.append(num%2)
  num//=2
bitlist.append(b1)
for i in range(2,n+1):
  num=l[-i]
  b1=[]
  while num!=0 or len(b1)<len(bitlist[0]):
    b1.append(num%2)
    num//=2
  bitlist.append(b1)
d={}
for i in range(len(bitlist[0])):
  d[i]=0
  for j in range(n):
    d[i]+=bitlist[j][i]
ans=0
table=[1]
for i in range(60):
  table.append((2*table[-1])%(10**9+7))
for i in d: 
  ans=(ans+table[i]*(n-d[i])*d[i])%(10**9+7)
print(ans)

### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
num=l[-1]
b1=[]

while num!=0:
  b1.append(num%2)
  num//=2
d={}
for i in range(len(b1)):
  d[i]=b1[i]

for i in range(2,n+1):
  num=l[-i]
  count=0
  while num!=0 or count<len(b1):
    d[count]+=num%2
    num//=2
    count+=1

ans=0
table=[1]
for i in range(60):
  table.append((2*table[-1])%(10**9+7))
for i in d: 
  ans=(ans+table[i]*(n-d[i])*d[i])%(10**9+7)
print(ans)
### BUGGY CODE ###

n,*x = map(int,open(0).read().split())
ans = 0
for i in range(n-1):
  for j in range(i+x[i]+1,n):
    if x[i] + x[j] == j - i :
      ans += 1
print(ans)

### FIXED CODE ###

n,*x = map(int,open(0).read().split())
ans = 0
xr = {}
xl = {}
for i in range(n):
  xrt = i+x[i]
  if xrt < n:
    if xrt in xr:
      xr[xrt] += 1
    else:
      xr[xrt] = 1
  xlt = i-x[i]
  if xlt >= 0:
    if xlt in xl:
      xl[xlt] += 1
    else:
      xl[xlt] = 1
for i in xr.keys():
  if i in xl:
    ans += xr[i]*xl[i]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

mod = 10**9+7

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

max_digit = 61

count_0 = [0 for _ in range(max_digit)]
count_1 = [0 for _ in range(max_digit)]

for i in range(len(a)):
    num_str = bin(a[i])[2:]
    # print(num_str)
    for j in range(len(num_str)):
        # print(num_str[-j-1])
        if num_str[-j-1] == "1":
            count_1[-j-1] += 1

# for i in range(max_digit):
#     count_0[i] = n-count_1[i]

ans = 0
count = 1
for i in range(61):
    # tmp = count_0[-i-1]*count_1[-i-1]
    tmp = count_1[-i-1]*(n-count_1[-i-1])
    ans += tmp*count
    count = (count*2) % mod
print(ans % mod)

### FIXED CODE ###

#!/usr/bin/env python3

# mod = 10**9+7

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

# max_digit = 61

# count_0 = [0 for _ in range(max_digit)]
# count_1 = [0 for _ in range(max_digit)]

# for i in range(len(a)):
#     num_str = bin(a[i])[2:]
#     # print(num_str)
#     for j in range(len(num_str)):
#         # print(num_str[-j-1])
#         if num_str[-j-1] == "1":
#             count_1[-j-1] += 1

# # for i in range(max_digit):
# #     count_0[i] = n-count_1[i]

# ans = 0
# count = 1
# for i in range(61):
#     # tmp = count_0[-i-1]*count_1[-i-1]
#     tmp = count_1[-i-1]*(n-count_1[-i-1])
#     ans += tmp*count
#     count = (count*2) % mod
# print(ans % mod)


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

mod = 10**9+7
max_digit = 61

ans = 0
m = 1
for _ in range(max_digit):
    bit = sum(x&m for x in a)
    bit //= m
    non_bit = n - bit
    ans = (ans+bit*non_bit*m)%mod
    m <<= 1
print(ans)
### BUGGY CODE ###

import numpy as np
import heapq
N_baito,M_days = map(int,input().split())
baitoList = np.array([list(map(int,input().split())) for i in range(N_baito)])
workList = []
hosyu = 0
for day in range(M_days+1):
    for baito in baitoList[baitoList[:,0]==day][:,1].tolist():
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)


### FIXED CODE ###

import heapq
N_baito,M_days = map(int,input().split())
hosyuList = [[] for _ in range(M_days)]

for _ in range(N_baito):
    days,hosyu = map(int,input().split())
    if days <= M_days:
        hosyuList[days-1].append(hosyu)

workList = []
hosyu = 0
for day in range(M_days):
    for baito in hosyuList[day]:
        heapq.heappush(workList,-1*baito)
    if workList:
        hosyu += heapq.heappop(workList)
print(-1*hosyu)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    for p in range(1000):
        pattern = str(p).zfill(3)
        key = 0
        cnt = 0
        for n in pattern:
            for i in range(key,N):
                if S[i] == n:
                    key = i+1
                    cnt += 1
                    break
        if cnt == 3:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    for p in range(1000):
        pattern = str(p).zfill(3)
        key = 0
        cnt = 0
        for n in pattern:
            for i in range(key,N):
                if S[i] == n:
                    key = i+1
                    cnt += 1
                    break
        if cnt == 3:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()