Problem:


Score : 400 points

Problem Statement

We have N integers. The i-th integer is A_i.

Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

2 \leq N \leq 3 \times 10^5

0 \leq A_i < 2^{60}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).

Sample Input 1

3
1 2 3

Sample Output 1

6

We have (1\mbox{ XOR } 2)+(1\mbox{ XOR } 3)+(2\mbox{ XOR } 3)=3+2+1=6.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

237

Sample Input 3

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

Sample Output 3

103715602

Print the sum modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc147/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
for i in range(0,60):
	a.append(0)

for i in range(0,n):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			a[j]+=1
		tmp=tmp//2

total=0
for j in range(60,0,-1):
	total*=2
	if(a[j-1]>0):
		total=total+(a[j-1])*(n-a[j-1])
	if(total>1000000007):
		total=total%1000000007
total=total%1000000007

print(total)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc141/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
for i in range(0,60):
	a.append(0)

for i in range(0,n):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			a[j]+=1
		tmp=tmp//2

total=0
for j in range(60,0,-1):
	total*=2
	if(a[j-1]>0):
		total=total+(a[j-1])*(n-a[j-1])
	if(total>1000000007):
		total=total%1000000007
total=total%1000000007

print(total)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc141/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
b=[]
c=[]
for i in range(0,60):
	a.append(0)

for i in range(0,n):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			a[j]+=1
		tmp=tmp//2

total=0
for j in range(60,0,-1):
	total*=2
	total=total+(a[j-1])*(n-a[j-1])
#	print(total)

total=total%1000000007

print(total)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#https://atcoder.jp/contests/abc141/tasks/abc147_d
import sys
#import collections

n= int(input())

tmp = input().split()
s = list(map(lambda a: int(a), tmp))

total=0
a=[]
b=[]
c=[]
for i in range(0,60):
	a.append(0)
	b.append(0)
	c.append(0)

tmp = s[0]
for j in range(0,60):
	if(tmp==0):
		break
	if(tmp%2==1):
		a[j]+=1
	tmp=tmp//2

tmp = s[n-1]
for j in range(0,60):
	if(tmp==0):
		break
	if(tmp%2==1):
		c[j]+=1
	tmp=tmp//2

for i in range(1,n-1):
	tmp = s[i]
	for j in range(0,60):
		if(tmp==0):
			break
		if(tmp%2==1):
			b[j]+=1
		tmp=tmp//2

#print(s)
#print(a)
#print(b)
#print(c)

total=0
for j in range(60,0,-1):
	total*=2
	total=total+(a[j-1]+b[j-1]+c[j-1])*(n-a[j-1]-b[j-1]-c[j-1])
#	print(total)

total=total%1000000007

print(total)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
cnt=[[0]*60 for i in range(2)]
for a in A:
    for i in range(60):
        if(a&(1<<i)):
            cnt[1][i]+=1
        else:
            cnt[0][i]+=1
res=0
for i in range(60):
    x = pow(2,i)
    x%=1000000007
    res+=cnt[1][i]*cnt[0][i]*x
    res%=1000000007
print(res)

Submission status: Time Limit Exceeded

Solution code:
def d():
  N = int(input())
  A = list(map(int,input().split()))

  num_ones = [0 for x in range(60)]
  for i in range(N):
    k = A[i]
    cnt = 0
    while k:
      num_ones[cnt] += k % 2
      cnt += 1
      k >>= 1

  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] * 2) % 1000000007)
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] & 1 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] >>= 1
  print(ans)
        
d()

Submission status: Time Limit Exceeded

Solution code:
def d():
  N = int(input())
  A = list(map(int,input().split()))

  num_ones = [0 for x in range(60)]
  for i in range(N):
    k = A[i]
    cnt = 0
    while k:
      num_ones[cnt] += k % 2
      cnt += 1
      k //= 2

  powers_of_two = [1]
  for i in range(1,60):
    powers_of_two.append((powers_of_two[-1] * 2) % 1000000007)
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] % 2 == 0:
        ans = (ans + powers_of_two[j] * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + powers_of_two[j] * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] //= 2
  print(ans)
        
d()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0
loop_count = len(format(max(A), "b"))

for i in range(loop_count):
    tmp = 0
    for ai in A:
        if ((1 << i) & ai) > 0:
            tmp += 1
    ans += (1 << i) * tmp * (N - tmp) % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

ans = 0
mem = {}
for i in range(N-1):
  for j in range(i+1, N):
    key = str(min(i,j)) + '-' + str(max(i,j))
    if key not in mem:
      mem[key] = (A[i]^A[j])%MOD
    ans += mem[key]
      
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[2**66+int(i) for i in input().split()]
ans=0
for i in range(64):
    x,y=0,0
    for j in a:
        if bin(j)[-i-1]=='1':
            y+=1
        else:
            x+=1
    ans+=x*y*(1<<i)
    ans%=10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_a = max(A)
bit_count = {}
for i in range(len(format(max_a, "b"))):
    bit_count[i] = [0, 0]
# 辞書の初期化が完了
max_value = i
zero_ume = "0" + str(len(format(max_a, "b"))) + "b"
for i in range(N):
    for j in reversed(range(len(format(A[i], zero_ume)))):
        if format(A[i], zero_ume)[j] == "0":
            bit_count[max_value-j][0] += 1
        else:
            bit_count[max_value-j][1] += 1
mod = 10**9+7
ans = 0
for k, v in bit_count.items():
    ans += (2**k) * v[0] * v[1] % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def d():
  N = int(input())
  A = list(map(int,input().split()))

  num_ones = [0 for x in range(60)]
  for i in range(N):
    k = A[i]
    cnt = 0
    while k:
      num_ones[cnt] += k % 2
      cnt += 1
      k //= 2
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] % 2 == 0:
        ans = (ans + (1 << j) * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + (1 << j) * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] //= 2
  print(ans)
        
d()

Submission status: Time Limit Exceeded

Solution code:
def d():
  from math import log2

  def get_ones(n):
    while n:
      k = n & -n
      yield int(log2(k))
      n ^= k

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

  num_ones = [0 for x in range(60)]
  for i in range(N):
    for j in get_ones(A[i]):
      num_ones[j] += 1
  
  ans = 0
  for i in range(N-1):
    for j in range(60):
      if A[i] % 2 == 0:
        ans = (ans + (1 << j) * num_ones[j]) % 1000000007
      else:
        num_ones[j] -= 1
        ans = (ans + (1 << j) * (N - i - 1 - num_ones[j])) % 1000000007
      A[i] //= 2
  print(ans)
        
d()

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
s = [0] * 60

for i in range(N):
    for j in range(60):
        if (A[i] >> j) & 1 == 1:
            s[j] += 1

ans = 0            
for i in range(60):
    ans += (((N - s[i]) * s[i]) << i) % mod
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(input().split(), np.int64)

ans = 0
for k in range(60):
  x = int(sum(A >> k & 1))
  ans += x * (N - x) * 2**k

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
binary = [0]*60
for inp in input().split():
    inp = bin(int(inp))[2:][::-1]
    for j, _inp in enumerate(inp):
        binary[j] += int(_inp)
    
ret = 0
pow2 = 1
for elem in binary:
    if elem == 0 or elem == N:
        pass
    else: 
        mn = elem * (N - elem) % (10**9 + 7)
        ret += pow2 * mn % (10**9 + 7)
    pow2 = pow2 * 2 % (10**9 + 7)
print(ret % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(j) for j in input().split()]

xor = []
for i in range(1, n):
    for j in range(i + 1, n + 1):
        xor.append(int(bin(a[i - 1] ^ a[j - 1]), 0))

print(sum(xor)%(pow(10, 9) + 7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
binary = [0]*60
for i in input().split():
    i = bin(int(i))[2:][::-1]
    for j in range(len(i)):
        binary[j] += int(i[j])
    
ret = 0
pow2 = 1
for elem in binary:
    m = elem # m < 10**9 + 7
    n = (N - elem) # n < 10**9 + 7
    mn = m * n % (10**9 + 7)
    ret += pow2 * mn % (10**9 + 7)
    pow2 = pow2 * 2 % (10**9 + 7)
print(ret % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=l[i][0]*l[i][1]*pow(2,i,mod)
    ans=ans%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=(2**i)*l[i][0]*l[i][1]
    ans=ans%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [[0 for _ in range(n)] for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            l[c][i] = int(a_s[c])
    for i in range(p):
        c1 = sum(l[i])
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0

for k in range(60):
  cnt = [0] * 2
  for i in range(N):
    ans += cnt[(A[i] >> k & 1) ^ 1] << k
    cnt[A[i] >> k & 1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    c1 = sum(l[i])
    ans += (2**(p - i - 1)) * c1 * (n - c1)
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(lambda x:list(map(int, reversed(bin(int(x) + 2**60)[2:]))), input().split()))

MOD = 10 ** 9 + 7

#print(a)
#exit()

ans = 0
d = 1
for j in range(60):
    x = 0
    for i in range(n):
        x += a[i][j]
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def pairORSum(arr, n,mod=10**9+7):
    ans = 0  # Initialize result

    # Consider all pairs (arr[i], arr[j)
    # such that i < j
    for i in range(0, n):

        for j in range(i + 1, n):
            ans = ans + (arr[i] ^ arr[j])
            ans %=mod

    return ans


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

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] >>= 1
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] //= 2
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=len(format(max(A),'b'))
Z=[0]*l
for a in A:
  a=format(a,'b').zfill(l)
  for i,ai in enumerate(a):
    if ai=='0':
      Z[i]+=1
x=1
ans=0
for z in Z[::-1]:
  ans+=x*(z*(N-z))
  x*=2
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(i) for i in input().split()]

s = [0]*61
for a in A:
    cnt = 0
    while a != 0:
        # print(cnt,a)
        if(a&1)==1:
            s[cnt+1] += 1
        cnt+=1
        a = a >> 1
ans = 0
for i in range(61):
    # print("a",2**(i-1)*s.get(i,0)*(n-s.get(i,0)))
    # print("b",s.get(i,0))
    # print("c",(n-s.get(i,0)))
    ans += (2**(i-1)*s[i]*(n-s[i])) % (10**9+7)
ans = ans % (10**9+7)
print(int(ans))
# print(s)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
l=len(format(A[-1],'b'))
Z=[0]*l
for a in A:
  a=format(a,'b').zfill(l)
  for i,ai in enumerate(a):
    if ai=='0':
      Z[i]+=1
x=1
ans=0
for z in Z[::-1]:
  ans+=x*(z*(N-z))
  x*=2
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
arr = np.array(l)
for i in range(p):
    c1 = np.count_nonzero(arr[i])
    ans += (2**(p - i - 1)) * c1 * (n - c1)
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
AtCoder Beginner Contest 147 D

https://atcoder.jp/contests/abc147/submissions/8876207
https://qiita.com/ZhangChaoran/items/0d59eb5c95cd9414801d


"""

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

# XORではビット毎に計算していくのが基本的な戦略
# 60乗までなので
bits = [0] * 60
for num in A:
    # A_i<2**60なので
    for i in range(60):
        # iビット目に1が立っていたらカウント
        if num & (1<<i):
            bits[i] += 1

"""
pは0からスタート
A_iについて、pビット目に1が立っていたら、i<jを満たすA_jのpビット目に0が立っている個数分2**pをプラスする
また、pビット目に0が立っていたら、i<jを満たすA_jのpビット目に1が立っている個数分2**pをプラスする
i,jのペアを見ていく時に、pビット目の1と0が何回出会うかを考えるとわかりやすいか
配列全体をみて、pビット目に1がa個ある場合、0はN-a個ある。これがΣΣのループで出会うので、
p桁目についてはa*(N-a)回2**pを答えに加えることになる
（a*(N-a)についてはあんまり腑に落ちてないが、例2とかで手を動かしてみるとそうなるので。）

これを全pに対して実施すると良い。
最後にmodを取ると値が大きすぎてあれなので、つどmodを取る
"""



ans = 0
for i, a in enumerate(bits):
    ans += a*(N-a) * 2**i
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    zero = 0
    for j in range(n):
        if l[i][j] == 0:
            zero += 1
    ans += (2**(p - i - 1)) * zero * (n - zero)
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    zero = 0
    one = 0
    for j in range(n):
        if l[i][j] == 0:
            zero += 1
        else:
            one += 1
    ans += (2**(p - i - 1)) * zero * one
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

def func(y, x):
    for i in range(60):
        if x == 0:
            continue
        y[i] += x & 1
        x = x >> 1
    return y

ys = reduce(func, xs, [0]*60)
ans = 0

for i,yi in enumerate(ys):
    ans += 2**(i) * yi * (n-yi)
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

y = [0]*60
for x in xs:
    for i in range(60):
        if x == 0:
            continue
        y[i] += x & 1
        x = x >> 1

ans = 0
for i,yi in enumerate(y):
    ans += 2**(i) * yi * (n-yi)
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
# for i in range(p):
#     print(l[i])
s = [[0 for _ in range(n+1)] for _ in range(p)]
for i in range(p):
    for j in range(n):
        s[i][j+1] = s[i][j] + l[i][j]
# for i in range(p):
#     print(s[i])
ans = 0
for j in range(n-1):
    for i in range(p):
        if l[i][j] == 1:
            ans += (2**(p - i - 1)) * ((n - j - 1) - (s[i][n] - s[i][j+1]))
        else:
            ans += (2**(p - i - 1)) * (s[i][n] - s[i][j+1])
        ans = ans % ((10**9) + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
# for i in range(p):
#     print(l[i])
s = [[0 for _ in range(n+1)] for _ in range(p)]
for i in range(p):
    for j in range(n):
        s[i][j+1] = s[i][j] + l[i][j]
# for i in range(p):
#     print(s[i])
ans = 0
for j in range(n-1):
    for i in range(p):
        if l[i][j] == 1:
            ans += ((2**(p - i - 1)) * ((n - j - 1) - (s[i][n] - s[i][j+1]))) % ((10**9) + 7)
        else:
            ans += ((2**(p - i - 1)) * (s[i][n] - s[i][j+1])) % ((10**9) + 7)
        ans = ans % ((10**9) + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
# for i in range(p):
#     print(l[i])
s = [[0 for _ in range(n+1)] for _ in range(p)]
for i in range(p):
    for j in range(n):
        s[i][j+1] = s[i][j] + l[i][j]
# for i in range(p):
#     print(s[i])
ans = 0
for j in range(n-1):
    for i in range(p):
        if l[i][j] == 1:
            ans += (2**(p - i - 1)) * ((n - j - 1) - (s[i][n] - s[i][j+1]))
        else:
            ans += (2**(p - i - 1)) * (s[i][n] - s[i][j+1])
        ans = ans % ((10**9) + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

ans = 0
for i in range(60):
    ones = 0
    for j in range(N):
        if ((A[j] >> i) & 1):
            ones += 1
    ans += 2**i * ones * (N - ones) % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = list(map(int,input().split()))
mod = 10**9+7
Ans = 0
for i in range(60):
  Po=0
  for j in A:
    if j>>i & 1:
      Po+=1
  Ans += Po*(N-Po)*(2**i)
  Ans = Ans % mod
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = list(map(int,input().split()))
mod = 10**9+7
Ans = 0
for i in range(60):
  Po=0
  Ne=0
  for j in A:
    if j>>i & 1:
      Po+=1
    else:
      Ne+=1
  Ans += Po*Ne*(2**i)
  Ans = Ans % mod
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
def xor(x,y):
    return (int(bin(x^y),2))
    
l=list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        ans+=xor(l[i],l[j])%(10**9+7)
        
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
def xor(x,y):
    return (int(bin(x^y),2))
    
l=list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        ans+=xor(l[i],l[j])
        
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = list(map(int,input().split()))
mod = 10**9+7
Ans = 0
for i in range(60+1):
  Po=0
  Ne=0
  for j in A:
    if j>>i & 1:
      Po+=1
    else:
      Ne+=1
  Ans += Po*Ne*(2**i)
  Ans = Ans % mod
print(Ans)

Submission status: Time Limit Exceeded

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

bit_count = [0] * 60
ans = 0
for a in A:
    for bit in range(60):
        if (a >> bit) & 1:
            count = bit_count[bit]
            ans += (2 ** bit) * (n-1-count*2)
            bit_count[bit] += 1
            ans %= mod
        else:
            continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  one = [0]*61
  zero = [0]*61
  for number in a:
    for i in range(61):
      if number >> i &1 == 1:
        one[i] +=1
      else:
        zero[i] += 1
  ans = 0
  mod = 10**9+7
  for i in range(61):
    ans += one[i]*zero[i]*int(2**i)%mod
    ans %= mod
  print(ans)
        
solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
suma=0
mod=10**9+7
for i in range(n):
  for j in range(i+1,n):
    suma+=(a[i]^a[j])%mod
print(suma%mod)

Submission status: Time Limit Exceeded

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

b = [0] * 60
for i in a:
    for j in range(60):
        b[j] += bool(i & (1 << j))
#print(b[j])
ans = 0
inf = int(1e9 + 7)
for i in range(60):
    ans += b[i] * (n - b[i]) * (1 << i) % inf
    ans %= inf
print(ans)

Submission status: Time Limit Exceeded

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

M = 10**9+7
ans = 0

def f(a, b, c):
    return a%M*b%M*c%M

for i in range(60):
    count = 0
    b = 1<<i
    for a in A:
        if (a&b) != 0:
            count += 1
    ans = (ans+f(count, N-count, b))%M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
N = int(readline())
A = [int(x) for x in readline().rstrip().split()]
B = [0] * 60
ans = 0
for i in range(N):
    i_bin = np.array(list(bin(A[i])))
    i_bin = i_bin[2:]
    i_bin = i_bin[::-1]
    k = 0
    for j in i_bin:
        if j == "1":
            B[k] += 1
        k += 1

for q in range(60):
    temp = B[q] * (N - B[q])
    ans += (temp % (7 + 10 ** 9)) * ((2 ** q) % (7 + 10 ** 9))
    ans %= 7 + 10 ** 9
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = [int(x) for x in readline().rstrip().split()]
B = [0] * 60
ans = 0
for i in range(N):
    i_bin = list(bin(A[i]))
    i_bin = i_bin[2:]
    i_bin = i_bin[::-1]
    k = 0
    for j in i_bin:
        if j == "1":
            B[k] += 1
        k += 1
B = np.array(B)

for q in range(60):
    temp = B[q] * (N - B[q])
    ans += (temp % (7 + 10 ** 9)) * ((2 ** q) % (7 + 10 ** 9))
    ans %= 7 + 10 ** 9
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
a=np.array(a)
suma=0
mod=10**9+7
for i in range(n):
  for j in range(i+1,n):
    tmp=np.bitwise_xor(a[i],a[j])%mod
    suma+=tmp
print(suma%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

N = int(input())

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


result = 0
Zcount = 0
Bit0 = 0
Bit1 = 0
while Zcount < 60:
    for i in range(0, len(A)):
        if A[i] % 2 == 0:
            Bit0 += 1
            A[i] //= 2
        else:
            Bit1 += 1
            A[i] //= 2
    result += (2 ** Zcount) * (Bit0 * Bit1)
    Zcount += 1
    Bit0 = 0
    Bit1 = 0
print(result % mod)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split(" ")))
s = 0
x = 10 ** 9 + 7
l = len(a)
for i in range(l):
  for j in range(i+1, l):
    s += a[i] ^ a[j]
    s %= x
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split(" ")))
s = 0
x = 10 ** 9 + 7
l = len(a)
for i in range(l):
  for j in range(i+1, l):
    s += a[i] ^ a[j]
    if s >= x:
      s = s % x
    

print(s % x)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split(" ")))
s = 0
l = len(a)
for i in range(l):
  for j in range(i+1, l):
    s += a[i] ^ a[j]

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
suma=0
mod=10**9+7
for i in range(n):
  for j in range(i+1,n):
    #print(i,j)
    suma+=(a[i]^a[j])%mod
print(suma%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
 
def jouyo(X):
    return X%1000000007
 
MAX=A[0]
for i in range(N):
    if MAX<=A[i]:
        MAX = A[i]
    else:
        MAX = MAX
 
p = 1
M = 1
for i in range(60):
    if 2*p <= MAX:
        p = 2*p
        M = M+1
    else:
        break
        
ans = 0
                
for i in range(1,M+1):
    count = 0
    for j in range(N):
        if A[j]%(2**i) >= 2**(i-1):
            count = count +1
    ans += jouyo(2**(i-1))*count*(N-count)
    ans = jouyo(ans)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
 
def jouyo(X):
    return X%1000000007
 
MAX=A[0]
for i in range(N):
    if MAX<=A[i]:
        MAX = A[i]
    else:
        MAX = MAX
 
p = 1
M = 1
for i in range(60):
    if 2*p <= MAX:
        p = 2*p
        M = M+1
    else:
        break
        
e=[]
for i in range(M+1):
  	e.append(2**i)
 
List = []        
for i in range(1,M+1):
    count = 0
    for j in range(N):
        if A[j]%e[i] >= e[i-1]:
            count = count +1
    List.append(count)
    
ans = 0   
for i in range(M):
    ans = jouyo(ans) + jouyo(jouyo(e[i])*jouyo(jouyo(List[i])*jouyo(N-List[i])))
    
print(jouyo(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
 
def jouyo(X):
    return X%1000000007
 
MAX=A[0]
for i in range(N):
    if MAX<=A[i]:
        MAX = A[i]
    else:
        MAX = MAX
 
p = 1
M = 1
for i in range(60):
    if 2*p <= MAX:
        p = 2*p
        M = M+1
    else:
        break
        
e=[]
for i in range(M+1):
  	e.append(2**i)
 
List = []        
for i in range(1,M+1):
    count = 0
    for j in range(N):
        if A[j]%e[i] >= e[i-1]:
            count = count +1
        else:
            count = count
    List.append(count)
    
ans = 0   
for i in range(M):
    ans = jouyo(ans) + jouyo(jouyo(e[i])*jouyo(jouyo(List[i])*jouyo(N-List[i])))
    
print(jouyo(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
 
def jouyo(X):
    return X%1000000007
 
MAX=A[0]
for i in range(N):
    if MAX<=A[i]:
        MAX = A[i]
    else:
        MAX = MAX
 
p = 1
M = 1
for i in range(60):
    if 2*p <= MAX:
        p = 2*p
        M = M+1
    else:
        break
        
e=[]
for i in range(M+1):
  	e.append(2**i)
 
List = []        
for i in range(1,M+1):
    count = 0
    for j in range(N):
        if A[j]%e[i] >= e[i-1]:
            count = count +1
        else:
            count = count
    List.append(count)
    
ans = 0   
for i in range(M):
    ans = jouyo(ans) + jouyo(jouyo(e[i])*jouyo(List[i])*jouyo((N-List[i])))
    
print(jouyo(ans))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(61):
    tmp_1 = 0
    tmp_0 = 0
    for k in range(N):
        if (A[k] >> i) & 1:
            tmp_1 += 1
        else:
            tmp_0 += 1
    ##print(i, tmp_1, tmp_0)
    ans += (tmp_1 * tmp_0) * (2 ** i)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N = int(input())
A = list(input().split())
d_to_num1 = {}
max_len = 0
for i in range(N):
    a = list(bin(int(A[i]))[2:])
    if max_len <= len(a):
        max_len = len(a)
    for j,b in enumerate(reversed(a)):
        if b=='1':
            if not(j in d_to_num1.keys()):
                d_to_num1[j]=1
            else:
                d_to_num1[j]+=1 
        
if __name__ == "__main__":
 
    res = 0
    mod = 10**9+7
 
    for i in range(max_len):
        if not(i in d_to_num1.keys()):
            num_1 = 0
        else:
            num_1 = d_to_num1[i]
        num_0 = (N-num_1)%mod
        tmp = num_1*num_0*pow(2,i,mod)
        res += tmp%mod
        res %= mod
    print(res)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

ans = 0
for k in range(60):
  c0 = 0
  c1 = 0
  for x in a:
    if bin(x)[2:].zfill(60)[-k - 1] == '1':
      c1 += 1
    else:
      c0 += 1

  ans += (c0 * c1) * (2 ** k)
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int, input().split()))
MAXBIT=60
MOD=10**9+7
bits=[[0 for _ in range(MAXBIT)] for _ in range(N)]
for i in range(N):
    tmp=A[i]
    j=0
    while tmp>0:
        bits[i][j]=tmp%2
        tmp=tmp//2
        j+=1
ans=0
for j in range(MAXBIT):
    cnt0=0
    for i in range(N):
        if bits[i][j]==0:
            cnt0+=1
    ans=(((cnt0*(N-cnt0))%MOD*(2**j))%MOD+ans)%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

A.sort()
sumv = 0
for i, vi in enumerate(A):
    for vj in A[i+1:]:
        sumv += vi^vj
    sumv %= mod
print(sumv)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
d = 1
total = 0
for _ in range(60):
  cnt = 0
  for each in A:
    cnt += (each & d) != 0
  total += cnt * (n-cnt) * d
  total %= mod
  d <<= 1
print(total)