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

import sys
import numpy as np
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
MOD = 1_000_000_007

def dot_MOD(x1, x2, MOD):
    """行列の積とＭＯＤ

    ＭＯＤを取りつつ行列の積をもとめる。

    Args:
        x1 (2Dndarry of int): 被積の行列
        x2 (2Dndarry of int): 加積の行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    if x1.shape[1] != x2.shape[0]:
        return 0
    ret = np.zeros((x1.shape[1],x2.shape[0]), dtype='int64')
    for i in range(x1.shape[0]):
        for j in range(x2.shape[1]):
            tem = np.mod(x1[i,:] * (x2[:,j][np.newaxis:]), MOD, dtype='int64')
            ret[i][j] = np.mod(tem.sum(), MOD, dtype='int64')
    return ret

N, K = map(int, input().split())
A = np.array(list(map(int, read().split())), dtype='int64').reshape((N, N))
ans = np.eye(N, dtype='int64')
while K:
    if K&1:
        ans = dot_MOD(ans,A,MOD)
    A = dot_MOD(A, A, MOD)
    K >>= 1
print(np.mod(ans.sum(), MOD, dtype='int64'))

### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
MOD = 1_000_000_007
def dot_MOD(x1, x2, MOD):
    """行列の積とＭＯＤ

    ＭＯＤを取りつつ行列の積をもとめる。

    Args:
        x1 (2Dndarry of int): 被積の行列
        x2 (2Dndarry of int): 加積の行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.zeros((x1.shape[1],x2.shape[0]), dtype='int64')
    for i in range(x1.shape[0]):
        for j in range(x2.shape[1]):
            ret[i][j] = np.mod(x1[i,:] * (x2[:,j][np.newaxis:]), MOD, dtype='int64').sum()
    ret %= MOD
    return ret

def x2_MOD(x, MOD):
    """行列の自冪とＭＯＤ

    ＭＯＤを取りつつ行列の自冪をもとめる。

    Args:
        x1 (2Dndarry of int): 行列

    Returns:
        ret (2Dndarry of int): 求まった行列

    Raises:
        例外の名前: 例外の説明 (例 : 引数が指定されていない場合に発生 )

    Yields:
        戻り値の型: 戻り値についての説明

    Examples:
        関数の使い方について記載

    Note:
        注意事項などを記載

    """
    ret = np.empty(x.shape, dtype='int64')
    for i in range(x.shape[0]):
        for j in range(x.shape[0]):
            ret[i][j] = np.mod(x[i,:] * (x[:,j][np.newaxis:]), MOD, dtype='int64').sum()
    ret %= MOD
    return ret

N, K = map(int, input().split())
A = np.array(list(map(int, read().split())), dtype='int64').reshape((N, N))
ans = np.eye(N, dtype='int64')
while K:
    if K&1:
        ans = dot_MOD(ans,A,MOD)
    A = x2_MOD(A, MOD)
    K >>= 1
print(np.mod(ans.sum(), MOD, dtype='int64'))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
S_list = list(S)

for i in range(Q):
    start, end = map(int, input().split())
    count = 0
    for j in range(start-1, end-1):
        if S_list[j] == "A" and S_list[j+1] == "C":
            count += 1
        else:
            pass
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
S_list = list(S)
count_list = [0]*N

for i in range(1, N):
    count_list[i] += count_list[i-1] 
    if S_list[i-1] == "A" and S_list[i] == "C":
        count_list[i] += 1

for i in range(Q):
    start, end = map(int, input().split())
    count = count_list[end-1] - count_list[start-1]
    print(count)
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    for _ in range(q):
        tmp = input()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten == 0:
                if tmp[2] == '1':
                    s = tmp[4] + s
                else:
                    s = s + tmp[4]
            else:
                if tmp[2] == '1':
                    s = s + tmp[4]
                else:
                    s = tmp[4] + s

    if hanten == 0:
        print(s)
    else:
        print(s[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

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

N=int(input())
power=1

for i in range(1,N+1):
    power=power*i

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


### FIXED CODE ###

def factorial(n):
    fact = 1
    for i in range(2, n+1):
        fact = (fact * i) % (10 ** 9 + 7)
    return fact
 
 
if __name__ == '__main__':
    n = int(input())
    print(factorial(n))
### BUGGY CODE ###

n=int(input())
A=[0]+list(map(int,input().split()))+[0]
for i in range(n):
  B=A[:i+1]+A[i+2:]
  print(sum(abs(B[j]-B[j+1]) for j in range(n)))

### FIXED CODE ###

n=int(input())
A=[0]+list(map(int,input().split()))+[0]
S=sum(abs(A[j]-A[j+1]) for j in range(n+1))
for i in range(n):
  if (A[i+1]-A[i])*(A[i+2]-A[i+1])>=0:
    print(S)
  else:
    print(S-abs(A[i+1]-A[i])-abs(A[i+2]-A[i+1])+abs(A[i+2]-A[i]))
### BUGGY CODE ###

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

ans = A
for i in range(A+1,B+1,1):
    ans = ans^i
print(ans)


### FIXED CODE ###

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

def XOR(A):
    # 0からAまでの排他的論理和を求める
    if A%4 == 0:
        return A
    elif A%4 == 2:
        return A+1
    elif A%4 == 1:
        return 1
    else:
        return 0

fA = XOR(A-1)
fB = XOR(B)
print(fB^fA)
### BUGGY CODE ###

L,R = map(int,input().split())

ans = 2019
for i in range(L,R):
  for j in range(i+1,R+1):
    ans = min(ans,(i*j)%2019)

print(ans)

### FIXED CODE ###

L,R = map(int,input().split())

ans = 2019
for i in range(L,min(L+2019,R)):
  for j in range(i+1,min(L+2019,R+1)):
    ans = min(ans,(i*j)%2019)

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

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
isRoot = [True] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    isRoot[b] = False

for i in range(n):
    if isRoot[i]:
        root = i
        break
INF = 10 ** 20
stack = [(root, -1, 0)]
height = [-INF] * n
parent = [None] * n
def search(stack):
    node, par, score = stack.pop()
    if score > height[node]:
        height[node] = score
        parent[node] = par
        for to in edges[node]:
            stack.append((to, node, score + 1))

while stack:
    search(stack)

for i in range(n):
    print(parent[i] + 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = -1
    index = -1
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = index

for i in range(n):
    print(parent[i] + 1)
### BUGGY CODE ###

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

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

print(sum % 1000000007)

### FIXED CODE ###

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

mod = 1000000007

S = [0]
for i in range(N):
    S.append((S[-1] + A[i]))

ans = 0
for i in range(N):
    sum = (S[N] - S[i + 1]) % mod
    ans += (A[i] * sum)
    ans %= mod

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

S = input()
Q = int(input())
q = [[i for i in input().split()] for j in range(Q)]

for i in range(Q):
    if q[i][0] == "1":
        S = S[::-1]
    elif q[i][0] == "2":
        if q[i][1] == "1":
            S = q[i][2] + S
        else:
            S = S + q[i][2]
            
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
q = [[i for i in input().split()] for j in range(Q)]

f = ""
l = ""
count = 0
for i in range(Q):
    if q[i][0] == "1":
        count += 1
    elif q[i][0] == "2":
        if count % 2 == 0:
            if q[i][1] == "1":
                f = q[i][2] + f
            else:
                l = l + q[i][2]
        else:
            if q[i][1] == "1":
                l = l + q[i][2]
            else:
                f = q[i][2] + f
        
if count % 2 == 0:
    print(f+S+l)
else:
    print((f+S+l)[::-1])
### BUGGY CODE ###

N=int(input())
S=input()
ans = 0
for i in range(N-2):
  for l in range(1,(N-i)//2+1):
    s = S[i:i+l]
    #print(i,l,s)
    if s in S[i+l:]:
      ans = max(ans,l)
print(ans)

    

### FIXED CODE ###

N=int(input())
S=input()
ans = 0
j = 0
for i in range(N):
  while j < N and S[i:j] in S[j:]:
    j += 1
  ans = max(ans,j-i-1)
print(ans)
### BUGGY CODE ###

N = int(input())
m = 0
for i in range(1, N):
    m += i % (i+1)
print(m)

### FIXED CODE ###

from decimal import Decimal
N = int(input())
print(Decimal(N * (N - 1) // 2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1
alis = [a2,a1]
for i in range(2,N+1):
    a = 0 if i in A else alis[-2]+alis[-1]
    alis.append(a)
print(1 if N == 1 else alis[-1]%1000000007)


### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

from bisect import bisect_left
def index(a, x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return True
    return False

R, G, B, N = map(int,input().split())
listB = [ i for i in range(N//B+1) ]
cnt = 0
for r in range(N//R+1):
    for g in range((N-R*r)//G+1):
        v = R*r+G*g
        if (N - v)%B == 0 and index(listB,(N - v)//B):
            cnt += 1
print(cnt)


### FIXED CODE ###

*j, N = map(int,input().split())
j.sort()
a,b,c = j
cnt = 0
for r in range(N//b+1):
    for g in range((N-b*r)//c+1):
        v = b*r+c*g
        if (N-v)%a == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N,K = map(int, input().split())
R,S,P = map(int, input().split())
T = [c for c in input()]
subs = [[] for _ in range(K)]

def max_sub(sub):
  total_point = 0
  previous = None
  for enemy_hand in sub:
    if previous == None:
      my_hand, point = battle(enemy_hand)
      total_point += point
      previous = my_hand
    else:
      my_hand, point = battle(enemy_hand)
      if my_hand == previous:
        previous = None
      else:
        total_point += point
        previous = my_hand
  return total_point

def battle(enemy_hand):
  if enemy_hand == "r":
    return "p", P
  elif enemy_hand == "s":
    return "r", R
  elif enemy_hand == "p":
    return "s", S
  else:
    raise ValueError("HAND IS WRONG")
    

for n in range(N):
  for k in range(K):
    if n % K == k:
      subs[k].append(T[n])

total_point = 0
for sub in subs:
  total_point += max_sub(sub)
  
      
print(total_point)

### FIXED CODE ###

N,K = map(int, input().split())
R,S,P = map(int, input().split())
T = [c for c in input()]

hand_points = {"p": P, "r": R, "s": S}

def win(enemy_hand):
  if enemy_hand == "r":
    return "p", P
  elif enemy_hand == "s":
    return "r", R
  elif enemy_hand == "p":
    return "s", S
  else:
    raise ValueError("HAND IS WRONG")

total_point = 0
my_hands = []
for enemy_hand in T:
  my_hand, point = win(enemy_hand)
  total_point += point
  my_hands.append(my_hand)

for i in range(K, N):
  my_hand = my_hands[i]
  if my_hand == my_hands[i-K]:
    total_point -= hand_points[my_hand]
    my_hands[i] = "any"

print(total_point)
### BUGGY CODE ###

n = int(input())
nim = []
for i in range(n):
  a,k = map(int,input().split())
  while a%k != 0 and a>k:
    t = a//k
    a -= t+1
  if a<k:
    x = 0
  elif a%k == 0:
    x = a//k
  nim.append(x)
ans = 0
for i in nim:
  ans ^= i
if ans == 0:
  print("Aoki")
else:
  print("Takahashi")

### FIXED CODE ###

n = int(input())
nim = []
for i in range(n):
  a,k = map(int,input().split())
  while a%k != 0 and a>k:
    t = a//k
    if t+1>=a%k:
      a -= t+1
    else:
      y = a%k
      a -= y//(t+1)*(t+1)
  if a<k:
    x = 0
  elif a%k == 0:
    x = a//k
  nim.append(x)
ans = 0
for i in nim:
  ans ^= i
if ans == 0:
  print("Aoki")
else:
  print("Takahashi")
### BUGGY CODE ###

def p_l_2():
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        for l in range(n - i):
            r = l + i
            if l == r:
                dp[l][r] = a[l]
            else:
                dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    print(dp[0][n - 1])


if __name__ == '__main__':
    p_l_2()


### FIXED CODE ###

def p_l_2():
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        for l in range(n - i):
            r = l + i
            if l == r:
                dp[l][r] = a[l]
            else:
                dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    print(dp[0][n - 1])


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

n, k = map(int, input().split())
c = []
for _ in range(n):
    a, b = map(int, input().split())
    c.extend([a]*b)
c.sort()
print(c[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
aa = []
for _ in range(n):
    a, b = map(int, input().split())
    aa.append([a, b])
aa.sort()
c = 0
for a, b in aa:
    if c < k:
        c += b
        if c >= k:
            ans = a
            break
print(ans)
### BUGGY CODE ###

import sys
N=input()
D=map(int,raw_input().split())
M=input()
T=map(int,raw_input().split())

D.sort()
T.sort()

#print N
#print D
#print M
#print T

no=0
for i in range(M):
	for j in range(no,N):
		#print i,j,T[i],D[j]
		if T[i]==D[j]:
			no=j+1
			break
		elif T[i]!=D[j] and j==N-1:
			print "NO"
			sys.exit()

print "YES"


### FIXED CODE ###

import sys
N=input()
a={}
for i in raw_input().split():
	#print i
	if i in a:
		a[i]=a[i]+1
	else:
		a[i]=1
#print a


M=input()
for j in raw_input().split():
	#print j
	if j in a:
		a[j]=a[j]-1
		if a[j]<0:
			print "NO"
			sys.exit()
	else:
			print "NO"
			sys.exit()		

print "YES"
### BUGGY CODE ###

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    dp = [[0] * (S + 1) for i in range(N + 1)]
    dp[0][0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp[i] = [2 * x for x in dp[i-1]]
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        for j in range(S + 1 - a):
            if dp[i-1][j] != 0:
                dp[i][j + a] += dp[i-1][j]
        
        # 大きくなりすぎないように逐次MODをとる
        for j in range(S + 1):
            dp[i][j] %= MOD

    # print(*dp, sep='\n')
    print(dp[N][S])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    # dp = [[0] * (S + 1) for i in range(N + 1)]
    # dp[0][0] = 1
    
    dp = np.zeros(S + 1, np.int64)
    dp[0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp_next = 2 * dp
        
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        dp_next[a:] += dp[:-a] # dp[:-a] = dp[:len(dp)-a]       

        # 大きくなりすぎないように逐次MODをとる
        dp_next %= MOD
        
        dp = dp_next

    # print(*dp, sep='\n')
    print(dp[S])

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

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

uniq_items = []
for i in set(A):
    uniq_items.append(A.count(i))

print(sum(sorted(uniq_items,reverse=True)[K:]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))

print(sum(sorted(Counter(A).values(),reverse=True)[K:]))
### BUGGY CODE ###

# 最大公約数
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

# 最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i])

sums = 0
mod = 10 ** 9 + 7
for i in range(N):
    sums += x // A[i]
    sums %= mod

print(sums)


### FIXED CODE ###

from fractions import gcd
# 最小公倍数
def lcm(x, y):
    return x // gcd(x, y) * y

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i]) 


sums = 0
mod = 10 ** 9 + 7
for i in range(N):
    sums += x // A[i]

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

import numpy as np
from numba import njit, i8

h, w, d = map(int, input().split())
arr = np.zeros([h, w], dtype=np.int64)

for i in range(h):
    arr[i] = list(map(int, input().split()))

q = int(input())
lr = np.zeros([q, 2], dtype=np.int64)

for i in range(q):
    lr[i] = list(map(int, input().split()))


@njit
def solve(h, w, d, arr):
    result = [[0] for _ in range(d)]
    for i in range(d):
        l = i
        score = 0
        while l + d <= h * w:
            if l == 0:
                result[i].append(score)
                l += d
                continue
            u = np.where(arr == l)
            v = np.where(arr == l + d)
            score += abs(v[0][0] - u[0][0]) + abs(v[1][0] - u[1][0])
            result[i].append(score)
            l += d
    return result


result = solve(h, w, d, arr)


for l, r in lr:
    print(result[l % d][r // d] - result[l % d][l // d])

### FIXED CODE ###

h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

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

for i in range(h):
    for j in range(w):
        s = a[i][j]
        arr[s] = (i, j)

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])
### BUGGY CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
tes = 0.0
SS = {sum(B[i:i+A[1]]):B[i:i+A[1]] for i in range(len(B)-A[1]+1)}
tes += sum([sum(i) for i in [[float(1/max(SS.values())[i]*x) for x in list(range(1,max(SS.values())[i]+1))] for i in range(len(max(SS.values())))]])
print(float(tes))

### FIXED CODE ###

A = list(map(int , input().split()))
B = list(map(int , input().split()))
kitaiti =[(i+1)/2 for i in B]
ans = []
dd = [0]
for i in range(A[0]):
    dd.append(dd[i] + kitaiti[i])
for i in range(A[1] , A[0]+1):
    ans.append(dd[i] - dd[i - A[1]])
print(max(ans))
### BUGGY CODE ###

from bisect import bisect, bisect_left
N = int(input())
A = list(map(int, input().split()))
A_ = sorted(list(set(A)))
A = sorted(A)
ans = 0
i = 0
while i < len(A_):
  a = A_[i]
  j = i+1
  while j < len(A_):
    if A_[j] % a == 0:
      A_.pop(j)
    else:
      j += 1
  if bisect(A, a)-bisect_left(A, a) > 1:
    ans -= 1
  i += 1
print(ans+len(A_))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
memo = [0]*(M+1)
i = 0
while i < N:
  a = A[i]
  memo[a] += 1
  x = a+a
  while x <= M:
    memo[x] += 2
    x += a
  i += 1
print(sum([1 if m == 1 else 0 for m in memo]))
### BUGGY CODE ###

n,m = map(int,input().split())
dic = {}
correct = penalty = 0
for i in range(m):
    p,s = input().split()
    if p not in dic:
        a = []
        a.append(s)
        dic[p] = a
    else:
        if 'AC' not in dic[p]:
            dic[p].append(s)
for p in dic:
    if 'AC' in dic[p]:
        correct += 1
        penalty += (len(dic[p])-1)
print(correct, penalty)

### FIXED CODE ###

n,m = map(int,input().split())
a = [False]*n
b = [0]*n
for i in range(m):
    p,s = input().split()
    p = int(p)
    if s == 'AC':
        a[p-1] = True
    if s == 'WA' and a[p-1] == False:
        b[p-1] += 1
correct = a.count(True)
penalty = 0
for i in range(len(a)):
    if a[i] == True:
        penalty += b[i]
print(correct, penalty)
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
sum = 0
a = np.array(list(map(int, input().split())))
for i in range(m):
    a = np.sort(a)[::-1]
    a[0] /= 2
for i in range(n):
    sum += (a[i] // 1)
print(sum)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

S = input()
Q = int(input())

rev_stetus = False
for _ in range(Q):
    ipt = input().split()
    if ipt[0] == "1":
        rev_stetus = not rev_stetus
    else:
        f = int(ipt[1])
        c = ipt[2]
        if rev_stetus:
            S = S + c if f == 1 else c + S
        else:
            S = c + S if f == 1 else S + c

if rev_stetus:
    print("".join(reversed(S)))
else:
    print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

rev_stetus = False
for _ in range(Q):
    ipt = input().split()
    if ipt[0] == "1":
        rev_stetus = not rev_stetus
    else:
        f = int(ipt[1])
        c = ipt[2]
        if rev_stetus:
            if f == 1:
                S.append(c)
            else:
                S.appendleft(c)
        else:
            if f == 1:
                S.appendleft(c)
            else:
                S.append(c)

if rev_stetus:
    S.reverse()
    print("".join(S))
else:
    print("".join(S))
### BUGGY CODE ###

from bisect import bisect_left
N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
if N==1:
  print(A[0]//(2**M))
else:
  while M>0:
    while M>0 and A[-1]>=A[-2]:
      A[-1]=A[-1]//2
      M-=1
    idx=bisect_left(A, A[-1])
    A.insert(idx, A[-1])
    A.pop()
  print(sum(A))

### FIXED CODE ###

import heapq
N, M=map(int, input().split())
A=list(map(int, input().split()))
A=list(map(lambda x: -x, A))
heapq.heapify(A)
for i in range(M):
  heapq.heappush(A, (heapq.heappop(A)+1)//2)
print(-sum(A))
### BUGGY CODE ###

def main():
    MOD=10**9+7
    n=int(input())
    x=[0 for i in range(60)]
    a=list(map(int,input().split()))

    for i in range(n):
        k=0
        while a[i]>0:
            if a[i]&1:
                x[k]+=1
            a[i]>>=1
            k+=1
    ans=0
    b=1
    for i in range(60):
        ans+=x[i]*(n-x[i])*b
        ans%=MOD
        b=(b*2)%MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD=10**9+7
    n=int(input())
    x=[0 for i in range(60)]
    a=list(map(int,input().split()))

    for i in range(n):
        k=0
        while a[i]>0:
            if a[i]&1:
                x[k]+=1
            a[i]>>=1
            k+=1
    ans=0
    b=1
    for i in range(60):
        ans+=x[i]*(n-x[i])*b
        ans%=MOD
        b=(b*2)%MOD
    print(ans)


if __name__ == '__main__':
    main()