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

import sys
input=sys.stdin.readline
class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
import itertools
xx=[i for i in range(n)]
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in itertools.combinations(xx,(n+1)//2):
  s=set(i)
  ac=[]
  bc=[]
  for j in range(n):
    if j in s:ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  m=[]
  for j in range(n):
    if j%2:
      x.append(bc[j//2][0])
      m.append(bc[j//2][1])
    else:
      x.append(ac[j//2][0])
      m.append(ac[j//2][1])
  f=False
  for j in range(1,n):
    if x[j-1]>x[j]:f=True
  if f:continue
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)


### FIXED CODE ###

class BinaryIndexedTree():
  def __init__(self,n):self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_1(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_1(j-1)
    if i!=0:a-=self.sum_1(i-1)
    return a
def tentousu(a):
  bit=BinaryIndexedTree(n)
  b=[0]*n
  for i in range(n):
    b[a[i]]=i
  ans=0
  for i in range(n):
    j=b[i]+bit.sum(b[i]+1,n)
    ans+=j-i
    bit.add(b[i],1)
  return ans
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(1,n,2):a[i],b[i]=b[i],a[i]
ans=inf=float('inf')
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  if s.count("0")!=n//2:continue
  ac=[]
  bc=[]
  for j in range(n):
    if s[j]=="1":ac.append((a[j],j))
    else:bc.append((b[j],j))
  ac.sort()
  bc.sort()
  x=[]
  for j in range(n):
    if j%2:x.append(bc[j//2])
    else:x.append(ac[j//2])
  f=False
  for j in range(1,n):
    if x[j-1][0]>x[j][0]:f=True
  if f:continue
  m=[]
  for j in range(n):m.append(x[j][1])
  ans=min(ans,tentousu(m))
if ans==inf:ans=-1
print(ans)
### BUGGY CODE ###

q = int(input())
for _ in range(q):
    x = input()
    y = input()
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    print(dp[m])



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

N = int(input())
D = [list(map(int, input().split())) for _ in range(N)]
A=0
B=0
for i in range(N):
  if i%2==0:
    D.sort(reverse=True)
    A+=D[0][0]
    D.pop(0)
  else:
    D.sort(reverse=True, key=lambda x:x[1])
    B+=D[0][1]
    D.pop(0)
  
print(A-B)

### FIXED CODE ###

N = int(input())
D=[]
b=0
for _ in range(N):
  A,B=map(int, input().split())
  D.append([A,B,A+B])
  b+=B
D.sort(reverse=True, key=lambda x:x[2])

ans=0
while D!=[]:
  ans+=D[0][2]
  D.pop(0)
  if D!=[]:
    D.pop(0)
  
print(ans-b)
### BUGGY CODE ###

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])
    tl, dl = zip(*sl)

    gmk = set()
    ce = []
    for s in sl[:k]:
        if s[0] in gmk:
            ce.append(s)
        gmk.add(s[0])

    gop = sum(dl[:k])
    bmk = max(len(set(tl)), k)

    gscr = len(gmk)**2 + gop

    ce.sort(key=lambda x: x[1])
    for c in ce[:bmk-len(gmk)]:
        for s in sl[k:]:
            if s[0] in gmk:
                continue
            k += 1
            gmk.add(s[0])
            gop = gop - c[1] + s[1]
            nscr = len(gmk)**2 + gop
            gscr = max(gscr, nscr)
            break

    return gscr


def main():
    n, k = list(map(int, input().split()))
    sl = [list(map(int, input().split())) for i in range(n)]
    print(r(n, k, sl))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])

    gmk = set()
    gop = 0
    ce = []
    for ti, di in sl[:k]:
        if ti in gmk:
            ce.append(di)
        gmk.add(ti)
        gop += di

    gscr = len(gmk)**2 + gop

    for ti, di in sl[k:]:
        if 0 >= len(ce):
            break
        if ti in gmk:
            continue
        gmk.add(ti)
        odi = ce.pop()
        gop = gop - odi + di
        nscr = len(gmk)**2 + gop
        gscr = max(gscr, nscr)

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [tuple(map(int, input().split())) for _ in range(n)]
    print(r(n, k, sl))


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

S = input()
Q = int(input())
Que = [list(input().split()) for _ in range(Q)]
r = 0
for q in Que:
    if q[0] == '1':
        r += 1
    else:
        if (q[1] == '1' and r % 2 == 0) or (q[1] == '2' and r % 2 == 1):
            S = q[2] + S
        else:
            S = S + q[2]
if r % 2 == 1:
    S = S[::-1]       
print(S)


### FIXED CODE ###

from collections import deque
S = input()
SS = deque()
for s in S:
    SS.append(s)
Q = int(input())
Que = [list(input().split()) for _ in range(Q)]
r = 0

for q in Que:
    if q[0] == '1':
        r += 1
    else:
        if (q[1] == '1' and r % 2 == 1) or (q[1] == '2' and r % 2 == 0):
            SS.append(q[2])
        else:
            SS.appendleft(q[2])
if r % 2 == 0:
   while len(SS) > 0:
        s = SS.popleft()
        print(s, end='')    
else:
    while len(SS) > 0:
        s = SS.pop()
        print(s, end='')
print('')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

res = [1 for _ in range(N+1)]

for x, y in combinations(range(1, N+1), 2):
    if find(x, 0) == find(y, 0) and find(x, 1) == find(y, 1):
        res[x] += 1
        res[y] += 1

print(" ".join(map(str, res[1:])))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def inpl(): return tuple(map(int, input().split()))
 
N, K, L = inpl()
 
tree = [[[-1, 1]  for _ in range(N+1)] for _ in range(2)] # [next, rank]

def find(i, t):
    if tree[t][i][0] == -1:
        group = i
    else:
        group = find(tree[t][i][0], t)
        tree[t][i][0] = group
    return group
 
def unite(x, y, t):
    px = find(x, t)
    py = find(y, t)
     
    if tree[t][px][1] == tree[t][py][1]: # rank is same
        tree[t][py][0] = px
        tree[t][px][1] += 1
    else:
        if tree[t][px][1] < tree[t][py][1]:
            px, py = py, px
        tree[t][py][0] = px
 
for _ in range(K):
    x, y = inpl()
    if not int(find(x, 0) == find(y, 0)):
        unite(x, y, 0)

for _ in range(L):
    x, y = inpl()
    if not int(find(x, 1) == find(y, 1)):
        unite(x, y, 1)

D = defaultdict(lambda: 0)
P = []
for i in range(1, N+1):
    a, b = find(i, 0), find(i, 1)
    D[(a, b)] += 1
    P.append((a, b))
print(" ".join(map(str, [D[(a, b)] for a, b in P])))
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
indices = [m.start(0) for m in re.finditer("AC", S)]

for _ in range(Q):
    li, ri = map(int, input().split())
    print(len([x for x in indices if li - 1 <= x and x < ri - 1]))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
count = 0
counts = [0 for _ in range(N)]

for i in range(N - 1):
    if S[i] == "A" and S[i + 1] == "C":
        count += 1
        counts[i + 1] = count
    else:
        counts[i + 1] = count

for _ in range(Q):
    li, ri = map(int, input().split())
    print(counts[ri - 1] - counts[li - 1])
### BUGGY CODE ###

H=10800
D=H*8
d=[0]*D
c=0
exec("a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b;"*input())
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)

### FIXED CODE ###

H=10800
D=H*8
d=[0]*D
c=0
for i in[0]*input():a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)
### BUGGY CODE ###

s = input()

def get_sum(J, I, L, K):
    if J > 0:
        total1 = I * 3 ** J + J * 3 ** (J - 1) # + 2 ** J
    else:
        total1 = I

    if L > 0:
        total2 = K * 3 ** L + L * 3 ** (L - 1) # + 2 ** L
    else:
        total2 = K
    return total1 * total2

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
    else:
        n_q_right.append(n_q_right[-1])

    if s[i] == 'A':
        n_a_right.append(n_a_right[-1] + 1)
    else:
        n_a_right.append(n_a_right[-1])

    if s[i] == 'C':
        n_c_right.append(n_c_right[-1] + 1)
    else:
        n_c_right.append(n_c_right[-1])

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_left = []
n_c_left = []
for i in range(len(n_q_right)):
    if s[i] == '?':
        n_q_left.append(n_q - n_q_right[i] - 1)
    else:
        n_q_left.append(n_q - n_q_right[i])
    if s[i] == 'C':
        n_c_left.append(n_c - n_c_right[i] - 1)
    else:
        n_c_left.append(n_c - n_c_right[i])

total = 0
for i in range(len(s)):
    if s[i] == 'B' or s[i]== '?':
        total += get_sum(n_q_right[i], n_a_right[i], n_q_left[i], n_c_left[i]) %  (10 ** 9 + 7)

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


### FIXED CODE ###

s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

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

import itertools as it
N=int(input())
L=list(map(int,input().split()))

count=0
L.sort()
A=list(it.combinations(L,3))

for a in A:
    if a[2]<a[0]+a[1]:
        count+=1

print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

#ABC154D
import sys

n, k = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))

total = 0
idx = 0
for i in range(n+1-k):
    tmp = sum(p[i:i+k])
    if total < tmp:
        total = tmp
        idx = i

ans = 0
for i in range(k):
    ans +=(1 + p[idx + i])/2

print(ans)

### FIXED CODE ###

#ABC154D
import sys
N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))

#print(P)

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2
#print(L)

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

#print(S)
total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x
    return True

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[]
ANS=N*(N-1)//2
flg=True
for i in range(M-1,-1,-1):
  if flg:
    ans.append(ANS-sum([x*(x-1)//2 for x in uf.all_group_numbers()]))
  else:
    ans.append(ans[-1])
  
  flg=uf.union(AB[i][0]-1,AB[i][1]-1)
for i in range(len(ans)-1,-1,-1):
  print(ans[i])

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False,0,0

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    nx=self.size(x)
    ny=self.size(y)
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    return True,nx,ny

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  flg,na,nb=uf.union(a-1,b-1)
  if flg:
    ans[i]=ans[i+1]-na*nb
  else:
    ans[i]=ans[i+1]
  i-=1
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

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

for i in range(n):
    for j in range(i+1, n):
        if A[i] > A[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    l = len(L)
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt += l-i

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
#print(*A)
print(str(cnt))
### BUGGY CODE ###

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


ACs=[]
WAs={}

AC=0
pena=0
for i in range(M):
  num, jud=input().split()
  
  if jud=="WA":
    if num not in WAs.keys():
      WAs[num]=1
    else:
      WAs[num]+=1
  else:
    if num not in ACs:
      ACs.append(num)
      AC+=1
      if num in WAs.keys():
        pena+=WAs[num]




"""
for i in range(M):
  if nums[i] in ACs:
    continue
  else:
    if jud[i]=="WA":
      WAs[nums[i]]+=1
    else:
      AC+=1
      ACs.append(nums[i])
      pena+=WAs[nums[i]]
"""      
print(AC, pena)


        

### FIXED CODE ###

N, M=map(int, input().split())
import numpy as np

pena=np.array([0]*N)
status=np.array([0]*N)


for i in range(M):
  p,s=tuple(input().split())
  p=int(p)
  if s=="WA":
    if status[p-1]!=1:
      pena[p-1]+=1
  if s=="AC":
    if status[p-1]!=1:
      status[p-1]=1
nac=sum(status)
npena=sum(pena*status)
print(nac, npena)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = [S]
ans[S][0] = 0
while q:
    now = q.pop()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)
### BUGGY CODE ###

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x

# nCk
K_MAX = 10**7
MOD = 10**9 + 7
fac, finv, inv = [0]*(K_MAX+1), [0]*(K_MAX+1), [0]*(K_MAX+1)
# nCk (k<=10^7, n<=10^9)
def com_init():
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2,K_MAX+1):
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k):
    ans = 1
    for i in range(n-k+1,n+1):
        ans *= i
        ans %= MOD
    return (ans * finv[k]) % MOD


com_init()
n, a, b = map(int, input().split()) 

all_comb = pow_k(2,n)
a_comb = com(n,a)
b_comb = com(n,b)

ans = all_comb - a_comb - b_comb -1
print(ans%MOD)


### FIXED CODE ###

def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x

# nCk
K_MAX = 10**7
MOD = 10**9 + 7
fac, finv, inv = [0]*(K_MAX+1), [0]*(K_MAX+1), [0]*(K_MAX+1)
# nCk (k<=10^7, n<=10^9)
def com_init():
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2,K_MAX+1):
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k):
    ans = 1
    for i in range(n-k+1,n+1):
        ans *= i
        ans %= MOD
    return (ans * finv[k]) % MOD


com_init()
n, a, b = map(int, input().split()) 

all_comb = pow_k(2,n)
a_comb = com(n,a)
b_comb = com(n,b)

ans = all_comb - a_comb - b_comb -1
print(ans%MOD)
### BUGGY CODE ###

# 目の前の人が同じ方を向いてたら幸福
# 操作はK回以下
# l~rの範囲内を列の塊ごと反転

n, k = map(int, input().split())
s = list(input())
# R = True, L = False
b = []
for i in range(n):
    if s[i] == 'R':
        b.append(True)
    else:
        b.append(False)

# s[i] != s[i+1] となる最小のiをまず見つけて
# s[i] == s[j] となるiより大きい最小のjを見つけて
# s[i+1]~s[j-1] の区間をひっくり返す
# 通常2点増えるのに対し端を含むと1点しか増えないので後回しにする

for i in range(n-2):
    if b[i] == b[i+1]:
        continue

    for j in range(i+2, n):
        if b[i] == b[j]:
            mir = list(map(lambda x: not x, b[j-1:i:-1]))
            b = b[:i+1]+mir+b[j:]
            k -= 1
            break

    if k == 0:
        break

happy = 0
for i in range(0, n-1):
    if b[i] == b[i+1]:
        happy += 1

# 端を含む操作は1回行えば十分なので両端が異なる&kが余ってたら+1点
if k > 0 and b[0] != b[n-1]:
    happy += 1

print(happy)


### FIXED CODE ###

# 今回の方針
# LRの境界の数だけで計算を済ませる

n, k = map(int, input().split())
s = list(input())

happy = 0
for i in range(0, n-1):
    if s[i] == s[i+1]:
        happy += 1

happy += 2*k
if happy >= n:
    happy = n-1

print(happy)
### BUGGY CODE ###


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sum = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            sum.append(A[x] + B[y] + C[z])

sum.sort(reverse=True)

for i in range(K):
    print(sum[i])

### FIXED CODE ###


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

sum = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            if (x+1)*(y+1)*(z+1) <= K:
                sum.append(A[x] + B[y] + C[z])
            else:
                break

sum.sort(reverse=True)
for i in range(K):
    print(sum[i])
### BUGGY CODE ###

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

mod = 10**9+7
ans = 0

for i in range(60):
  B = list(map(lambda x:x%pow(2,(i+1))//pow(2,i), A))
  one = sum(B)
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import numpy as np
mod = 10**9+7
ans = 0
A = np.array(A)
for i in range(60):
  one = np.count_nonzero(A>>i&1)
  zero = N - one
  ans += one*zero*pow(2,i)
  ans %= mod
  #print(one,zero)

print(ans)