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

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1



if __name__ == '__main__':

    n = int(input())
    T = HashTable(n)
    char2num = str.maketrans("ACGT", "1234")

    for _ in range(n):
        command, char = input().split(" ")
        num = int(char.translate(char2num))
        if command == "insert":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

n = int(input())
print(sum([1 if str(i).count('3') > 0 and str(i).count('5') > 0 and str(i).count('7') > 0 and len(str(i)) == str(i).count('3') + str(i).count('5') + str(i).count('7') else 0 for i in range(1,n+1)]))

### FIXED CODE ###

import itertools
n = int(input())
l = []
l.extend(list(itertools.product([3,5,7], repeat=i)) for i in range(3,10))
l = [int("".join(map(str,j))) for i in l for j in i if 7 in j and 5 in j and 3 in j]
print(sum([1 for i in l if n>=i]))
### BUGGY CODE ###

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

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

ans = x

i = 1
a_list = [x]
a = x
flag = 0
while(i<n):
    a = (a*a) % m
    if a in a_list:
        flag = 1
        break
    a_list.append(a)
    ans += a
    i+=1
    
if flag == 1:
    b = a_list.index(a)
    tmp_sum = 0
    for j in range(b,len(a_list)):
        tmp_sum += a_list[j]
    blen = len(a_list)-b
    ans += tmp_sum*((n-i)//blen)
    for k in range((n-i) % blen):
        ans += a_list[i+k-blen]

print(ans)

### FIXED CODE ###

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

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

a_list = [x]
a = x
i = 1
while (i<n and i < m+1):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

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

N, Q = [int(x) for x in input().split()]
S = input()

SD = {}
for i in range(len(S)):
    a = SD.get(S[i], set())
    a.add(i)
    SD[S[i]] = a

G = [1] * N

D = {}
rmg = 0
for _ in range(Q):
    t, d = input().split()
    # print(G)

    if SD.get(t,0) == 0:
        continue

    if d == "L":
        for i in SD[t]:
            if i == 0:
                rmg += G[i]
                G[i] = 0
            else:
                G[i - 1] += G[i]
                G[i] = 0
    else:
        for i in SD[t]:
            if i == N - 1:
                rmg += G[i]
                G[i] = 0
            else:
                G[i + 1] += G[i]
                G[i] = 0

# print(G)

print(N - rmg)


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
S = input()
TD = []
for _ in range(Q):
    t, d = input().split()
    TD.append((t, d))


def isDead(targetIdx):
    ti = targetIdx
    for t, d in TD:
        if t == S[ti]:
            if d == 'L':
                ti -= 1
                if ti == -1:
                    return -1
            else:
                ti += 1
                if ti == N:
                    return +1
    return 0


l, t, r = 0, N // 2, N - 1

while r - l > 1:
    t = (l + r) // 2
    if isDead(t) == -1:
        l = t
    else:
        r = t

L = l
if L == 0 and isDead(0) == 0:
    L -= 1

l, t, r = 0, N // 2, N - 1

while r - l > 1:
    t = (l + r) // 2
    if isDead(t) == +1:
        r = t
    else:
        l = t

R = r
if R == N - 1 and isDead(N - 1) == 0:
    R += 1

print(R - L - 1)

# print((L, R))
# print([isDead(t) for t in range(N)])
### BUGGY CODE ###

n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
    s,t=map(int,input().split())
    ans[s-1]+=t

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop(0)
  flag[v]=True
  for i in lst[v]:
    if flag[i]:
      continue
    flag[i]=True
    ans[i]+=ans[v]
    Q.append(i)


print(' '.join([str(i) for i in ans]))


### FIXED CODE ###

n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
    s,t=map(int,input().split())
    ans[s-1]+=t

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop()
  flag[v]=True
  for i in lst[v]:
    if flag[i]:
      continue
    flag[i]=True
    ans[i]+=ans[v]
    Q.append(i)


print(' '.join([str(i) for i in ans]))
### BUGGY CODE ###

N = int(input())
S = "0"+input()
lr = [0]
lg = [0]
lb = [0]
for j in range(1,N+1):
  if S[j] == "R":
    i = j-1
    lr.append(lr[i]+1)
    lg.append(lg[i])
    lb.append(lb[i])
  if S[j] == "G":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i]+1)
    lb.append(lb[i])
  if S[j] == "B":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i])
    lb.append(lb[i]+1)

cnt = 0
mcnt = 0
for i in range(1,N+1):
  s = S[i]
  for j in range(1,N-i+1): 
    #Rパターン
    if s == "R":      
      if S[i+j] == "R":
        continue
      else:
        if i+j <= N and i-j >=0:
          if (S[i+j] == "B" and S[i-j] == "G") or (S[i+j] == "G" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "G":
          cnt += lb[i-1]
        if S[i+j] == "B":
          cnt += lg[i-1]
    #Gパターン
    if s == "G":      
      if S[i+j] == "G":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "B" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lb[i-1]
        if S[i+j] == "B": 
          cnt += lr[i-1]   
    #Bパターン
    if s == "B":      
      if S[i+j] == "B":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "G" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "G"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lg[i-1]
        if S[i+j] == "G": 
          cnt += lr[i-1]  
print(cnt+mcnt)

### FIXED CODE ###

N = int(input())
S = "0"+input()
lr = [0]
lg = [0]
lb = [0]
for j in range(1,N+1):
  if S[j] == "R":
    i = j-1
    lr.append(lr[i]+1)
    lg.append(lg[i])
    lb.append(lb[i])
  if S[j] == "G":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i]+1)
    lb.append(lb[i])
  if S[j] == "B":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i])
    lb.append(lb[i]+1)

cnt = 0
mcnt = 0
for i in range(1,N+1):
  s = S[i]
  for j in range(1,N-i+1): 
    #Rパターン
    if s == "R":      
      if S[i+j] == "R":
        continue
      else:
        if i+j <= N and i-j >=0:
          if (S[i+j] == "B" and S[i-j] == "G") or (S[i+j] == "G" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "G":
          cnt += lb[i-1]
        if S[i+j] == "B":
          cnt += lg[i-1]
    #Gパターン
    if s == "G":      
      if S[i+j] == "G":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "B" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lb[i-1]
        if S[i+j] == "B": 
          cnt += lr[i-1]   
    #Bパターン
    if s == "B":      
      if S[i+j] == "B":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "G" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "G"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lg[i-1]
        if S[i+j] == "G": 
          cnt += lr[i-1]  
print(cnt+mcnt)
### BUGGY CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif X>0 and D<X and K*D<X:
    ans=X-K*D
else:
    ans=X
    for i in range(0,K):
        ans=ans-D
        if ans<0 and (K-i)%2==0:
            ans=ans+D
            break
        elif ans<0 and (K-i)%2==1:
            ans=-ans
            break
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
answer = [-1] * N
p = []
for i in range(N):
  count[i]  = A.count(i + 1)

for i in range(N):
  if answer[A[i] - 1] != -1:
    p.append(answer[A[i] - 1])
  else:
    count[A[i] - 1] -= 1
    s = 0
    for j in range(N):
      s += count[j] * (count[j] - 1) // 2
    p.append(s)
    count[A[i] - 1] += 1

for i in p:
  print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)
### BUGGY CODE ###

import collections
sum = 0
#Asum=[]
N = int(input())
A =  [int(N) for N in input().split()]
B = A.copy()
for i in range(N):
    B.pop(i)
    c = collections.Counter(B)
    values, counts = zip(*c.most_common())
    for j in range(len(counts)):
        if counts[j]>1:
            sum+=int(counts[j]*(counts[j]-1)/2)
        else:
            break
    B=A.copy()
    #Asum.append(sum)
    print(sum)
    sum=0
#for k in range(N):
    #print(Asum[k])

### FIXED CODE ###

from collections import Counter
def choose2(n):
    return n*(n-1)/2
sum1=0
sum2=0
N = int(input())
A = [int(N) for N in input().split()]
S = Counter(A)
for i in  S.values():
    sum1+=int(choose2(i))
for j in range(N):
    sum2+=int(sum1-choose2(S[A[j]])+choose2(S[A[j]]-1))
    print(sum2)
    sum2=0
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
	s.append("".join(sorted([a for a in input()])))
pair = 0
for i in range(N-1):
	for j in range(i+1, N):
		if s[i] == s[j]:
			pair += 1
print(pair)

### FIXED CODE ###

def main():
	N = int(input())
	s = {}
	pair = 0
	for _ in range(N):
		b = "".join(sorted([a for a in input()]))
		if b in s.keys():
			pair += s[b]
			s[b] += 1
		else:
			s[b] = 1
	print(pair)
main()
### BUGGY CODE ###

n,k = map(int, input().split())
dp = [float("inf")] * n
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int, input().split())
dp = [float("inf")] * 100000
h = list(map(int, input().split()))
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

if(max1 > n+1):
  for i in reversed(range(n+1)):
    rest1 = y-i*1000
    max2 = int((rest1)/5000) + 1
    for ii in reversed(range(max2)):
      rest2 = y-i*1000-ii*5000
      mod = rest2%10000
      iii = int(rest2/10000)
      tot = i+ii+iii
      if(mod == 0 and tot == n):
        print(iii, ii, i)
        sys.exit()
else:
  for i in reversed(range(max1)):
    rest1 = y-i*1000
    max2 = int((rest1)/5000) + 1
    for ii in reversed(range(max2)):
      rest2 = y-i*1000-ii*5000
      mod = rest2%10000
      iii = int(rest2/10000)
      tot = i+ii+iii
      if(mod == 0 and tot == n):
        print(iii, ii, i)
        sys.exit()

print(-1,-1,-1)

### FIXED CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in range(max1):
  rest = y-i*9000-n*1000
  mod = rest%4000
  ii  = int((rest)/4000)
  iii = n-i-ii
  if(mod == 0 and iii>=0 and ii>=0):
    print(i, ii, iii)
    sys.exit()
    
print(-1,-1,-1)
### BUGGY CODE ###

import math

n=int(input())
for i in range(int(math.sqrt(n)),n+1):
    if n%i==0:print(max(len(str(i)),len(str(n//i))));break

### FIXED CODE ###

import math

n=int(input())
for i in range(int(math.sqrt(n)),0,-1):
    if n%i==0:print(max(len(str(i)),len(str(n//i))));break
### BUGGY CODE ###

import math
N=int(input())
S=input().split()
list=[]
for i in range(0,N):
  list.append(int(S[i]))
list.sort()
ans=0
for i in range(0,N-2):
  a=list[i]
  for j in range(i+1,N-1):
    b=list[j]
    L=j+1
    R=N-1
    while True:
      if L==R or R==L+1:
        break
      if list[math.floor((L+R)/2)]>=a+b:
        R=math.floor((L+R)/2)
      else:
        L=math.floor((L+R)/2)
    if list[L]>=a+b:
      ans=ans+L-j-1
    else:
      if list[R]>=a+b:
        ans=ans+L-j
      else:
        ans=ans+R-j
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
 
count = 0
for i in range(n):
  for j in range(i+1,n):
    index = bisect.bisect_left(l,l[i]+l[j])
    count += index - j - 1
    
print(count)
### BUGGY CODE ###

def dfs(inParam, digits, lunlunCount, lunlun):
    if len(inParam) != digits:
        if int(inParam[len(inParam)-1]) == 0:
            nextNumList = [0, 1]
        elif int(inParam[len(inParam)-1]) == 9:
            nextNumList = [8, 9]
        else:
            nextNum = int(inParam[len(inParam)-1])
            nextNumList = [nextNum-1, nextNum, nextNum+1]
        
        for item in nextNumList:
            myTupp = dfs(inParam+str(item), digits, lunlunCount, lunlun)
            lunlunCount = myTupp[0]
            if myTupp[2] == 'e':
                return myTupp
        
        return myTupp
    
    else:
        lunlunCount += 1
        state = 'c'

        if lunlunCount == lunlun:
            state = 'e'
            print(inParam)

        return (lunlunCount, inParam, state)

K = int(input())

mylunlun = 0
mydigits = 1
while mylunlun != K:
    for indx in range(1, 10):
        mylunlun, lunlunNumber, _ = dfs(str(indx), mydigits, mylunlun, K)
        # if mylunlun == K:
        #     break
    
    if mylunlun == K:
        break

    mydigits += 1


### FIXED CODE ###

def dfs(inParam, digits, lunlunCount, lunlun):
    if len(inParam) != digits:
        if int(inParam[len(inParam)-1]) == 0:
            nextNumList = [0, 1]
        elif int(inParam[len(inParam)-1]) == 9:
            nextNumList = [8, 9]
        else:
            nextNum = int(inParam[len(inParam)-1])
            nextNumList = [nextNum-1, nextNum, nextNum+1]
        
        for item in nextNumList:
            myTupp = dfs(inParam+str(item), digits, lunlunCount, lunlun)
            lunlunCount = myTupp[0]
            if myTupp[2] == 'e':
                return myTupp
        
        return myTupp
    
    else:
        lunlunCount += 1
        state = 'c'

        if lunlunCount == lunlun:
            state = 'e'
            print(inParam)

        return (lunlunCount, inParam, state)

K = int(input())

mylunlun = 0
mydigits = 1
while mylunlun != K:
    for indx in range(1, 10):
        mylunlun, lunlunNumber, _ = dfs(str(indx), mydigits, mylunlun, K)
        if mylunlun == K:
            break
    
    if mylunlun == K:
        break

    mydigits += 1
### BUGGY CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
xy=[0]*n
for i in range(n):
    x,y=map(int,input().split())
    xy[i]=[x,y,i]

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################

xy.sort()
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append([x2-x1,n2])
    edge[n2].append([x2-x1,n1])

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append([x2-x1,n2])
    edge[n2].append([x2-x1,n1])

print(prim_heap())

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
xy=[0]*n
for i in range(n):
    x,y=map(int,input().split())
    xy[i]=[x,y,i]

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################

xy.sort()
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

print(prim_heap())
### BUGGY CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


print(ans)
    
     


### FIXED CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [((A[i]>>(59-j))) & 1 for j in range(60)]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


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

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
events = []
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    events.append((s - x, 2, x))
    events.append((t - x, 1, x))
for line in lines[n:]:
    events.append((int(line), 3))
events.sort()

constructing = set()
buf = []
for ev in events:
    if ev[1] == 2:
        constructing.add(ev[2])
    elif ev[1] == 1:
        constructing.remove(ev[2])
    else:
        buf.append(min(constructing) if constructing else -1)
print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n=int(input())
p=list(map(float,input().split()))

dp=[[0.0]*(n+1) for i in range(n+1)]
dp[0][0]=1.0

for i in range(n):
 for j in range(n):
  dp[i+1][j+1]+=dp[i][j]*p[i]
  dp[i+1][j]+=dp[i][j]*(1-p[i])

print(sum(dp[-1][(n+1)//2:]))

### FIXED CODE ###

n=int(input())
p=list(map(float,input().split()))

dp=[[0.0]*(n+1) for i in range(n+1)]
dp[0][0]=1.0

for i in range(n):
 for j in range(n):
  dp[i+1][j+1]+=dp[i][j]*p[i]
  dp[i+1][j]+=dp[i][j]*(1-p[i])

print(sum(dp[-1][(n+1)//2:]))