We define f (X, Y) as number of different corresponding bits in binary representation of X and Y. For example, f (2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f (2, 7) = 2.
You are given an array A of N integers, A_{1}, A_{2} ,…, A_{N}. Find sum of f(A_{i}, A_{j}) for all ordered pairs (i, j) such that 1 ≤ i, j ≤ N. Return the answer modulo 10^{9}+7.
Example 1:
Input: N = 2
A = {2, 4}
Output: 4
Explaintion: We return 
f(2, 2) + f(2, 4) + 
f(4, 2) + f(4, 4) = 
0 + 2 + 
2 + 0 = 4.
Example 2:
Input: N = 3
A = {1, 3, 5}
Output: 8
Explaination: We return 
f(1, 1) + f(1, 3) + f(1, 5) + 
f(3, 1) + f(3, 3) + f(3, 5) + 
f(5, 1) + f(5, 3) + f(5, 5) = 
0 + 1 + 1 + 
1 + 0 + 2 + 
1 + 2 + 0 = 8.
Your Task:
You do not need to read input or print anything. Your task is to complete the function countBits() which takes the value N and the array A as input parameters and returns the desired count modulo 10^{9}+7.
Expected Time Complexity: O(N * log_{2}(Max(A_{i})))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
2^{0} ≤ A[i] < 2^{31}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:
    def countBits(self, N, A):
        # code here

Solutions:
MOD = 1000000007

class Solution:

	def countBits(self, N, A):
		MOD = 1000000007
		result = 0
		for i in range(32):
			count = 0
			for j in range(N):
				if A[j] & 1 << i:
					count += 1
			result += count * (N - count) * 2
		return result % MOD


class Solution:

	def countBits(self, N, A):
		m = 1000000007
		cnt = 0
		maxi = max(A)
		z = len(bin(maxi)[2:])
		li = [bin(x)[2:].zfill(z) for x in A]
		l = [0 for i in range(z)]
		for x in li:
			i = 0
			for ch in x:
				if ch == '0':
					l[i] += 1
				i += 1
		for x in l:
			cnt += 2 * x * (N - x) % m
		return cnt % m


class Solution:

	def countBits(self, N, A):
		M = 1000000000.0 + 7
		res = 0
		for i in range(32):
			z = 0
			for j in range(N):
				if A[j] & 1 << i:
					z += 1
			res += z * (N - z) * 2
		return int(res % M)


from collections import defaultdict

class Solution:

	def countBits(self, N, A):
		p = 10 ** 9 + 7
		res = 0
		one_cnts = [0 for _ in range(64)]
		for (i, num) in enumerate(A):
			for j in range(64):
				if num & 1 << j:
					res += i - one_cnts[j]
				else:
					res += one_cnts[j]
				res %= p
			n = num
			j = 0
			while n:
				if n & 1:
					one_cnts[j] += 1
				n >>= 1
				j += 1
		return 2 * res % p


class Solution:

	def countBits(self, N, A):
		out = 0
		for i in range(32):
			count = 0
			for j in range(N):
				if A[j] & 1 << i:
					count += 1
			out += count * (N - count) * 2


class Solution:

	def countBits(self, N, A):
		mod = 1000000007
		ans = 0
		for i in range(31):
			count = 0
			for j in A:
				if j & 1 << i:
					count += 1
			ans += count * (N - count) * 2
			ans %= mod
		return ans


class Solution:

	def countBits(self, N, A):
		res = 0
		for i in range(32):
			count1 = 0
			for j in range(N):
				bit = 1 << i
				if A[j] & bit == 0:
					count1 += 1
			res += count1 * (N - count1) * 2
		return res % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		ans = 0
		m = 10 ** 9 + 7
		for i in range(0, 32):
			z = 0
			o = 0
			for j in A:
				if 1 << i & j == 0:
					z += 1
				else:
					o += 1
			ans += z * o
			ans %= m
		return ans * 2 % m


def countNoOfBits(num):
	count = 0
	while num > 0:
		num = num >> 1
		count += 1
	return count

class Solution:

	def countBits(self, N, A):
		maxBits = countNoOfBits(max(A))
		count1 = 0
		count0 = 0
		mask = 1
		ans = 0
		while maxBits > 0:
			for i in range(N):
				if A[i] & mask > 0:
					count1 += 1
				else:
					count0 += 1
			ans += count1 * count0 * 2
			count1 = 0
			count0 = 0
			mask = mask << 1
			maxBits = maxBits - 1
		return ans % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		arr = [0] * 35
		for i in A:
			pos = 0
			while i:
				if i & 1:
					arr[pos] += 1
				pos += 1
				i = i >> 1
		count = 0
		for i in arr:
			count = (count + i * (N - i) * 2) % 1000000007
		return count


class Solution:

	def countBits(self, n, arr):
		ans = 0
		for i in range(0, 32):
			count = 0
			for j in range(0, n):
				if arr[j] & 1 << i:
					count += 1
			ans += count * (n - count) * 2
		return ans % 1000000007


class Solution:

	def countBits(self, N, A):
		ans = 0
		for i in range(32):
			countOn = 0
			for j in range(N):
				if A[j] & 1 << i != 0:
					countOn += 1
			countOff = N - countOn
			diff = countOn * countOff * 2
			ans += diff
		return ans % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		maxOfA = max(A)
		ans = 0
		while maxOfA > 0:
			countOfZero = 0
			countOfOne = 0
			for i in range(N):
				lastBit = A[i] & 1
				if lastBit == 0:
					countOfZero += 1
				else:
					countOfOne += 1
				A[i] = A[i] >> 1
			ans += countOfZero * countOfOne * 2
			maxOfA = maxOfA >> 1
		return ans % 1000000007


class Solution:

	def countBits(self, N, A):
		res = 0
		MOD = 10 ** 9 + 7
		for i in range(32):
			bt = 1 << i
			c = 0
			for v in A:
				if v & bt:
					c += 1
			res = (res + 2 * c * (N - c)) % MOD
		return res % MOD


class Solution:

	def countBits(self, N, A):
		mod = pow(10, 9) + 7
		total = 0
		for i in range(0, 32):
			count = 0
			for v in A:
				if v & 1 << i:
					count += 1
			total = (total + count * (N - count) * 2) % mod
		return total


class Solution:

	def countBits(self, N, A):
		res = 0
		m = 10 ** 9 + 7
		for i in range(32):
			cone = 0
			for j in range(N):
				if A[j] & 1 << i:
					cone += 1
			res = (res % m + 2 * cone * (N - cone) % m) % m
		return res


class Solution:

	def countBits(self, N, A):
		bits = [[0 for i in range(32)], [0 for i in range(32)]]
		for i in A:
			power = 0
			while i > 1:
				bits[i % 2][power] += 1
				i //= 2
				power += 1
			bits[1][power] += 1
			for j in range(power + 1, 32):
				bits[0][j] += 1
		ans = 0
		for i in range(32):
			ans = (ans + bits[0][i] * bits[1][i]) % (10 ** 9 + 7)
		return ans * 2 % (10 ** 9 + 7)


class Solution:

	def countBits(self, n, arr):
		ans = 0
		mod = 1000000000.0 + 7
		for i in range(32):
			(zero, one) = (0, 0)
			for num in arr:
				if num & 1 << i:
					one += 1
				else:
					zero += 1
			ans += int(one * zero % mod)
			ans = int(ans % mod)
		return int(2 * ans % mod)


class Solution:

	def countBits(self, N, A):
		ma = len(bin(max(A))) - 2
		ar0 = [0 for x in range(ma)]
		ar1 = [0 for x in range(ma)]
		for x in A:
			for y in range(ma):
				bit = x & 1
				if bit == 1:
					ar1[y] += 1
				else:
					ar0[y] += 1
				x = x >> 1
		c = 0
		for x in range(ma):
			c += ar0[x] * ar1[x]
		return c * 2 % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		c = 0
		m = pow(10, 9) + 7
		for i in range(32):
			set0 = 0
			set1 = 0
			for i in range(N):
				if A[i] & 1:
					set1 += 1
				else:
					set0 += 1
				A[i] = A[i] >> 1
			c += set0 * set1 * 2
		return c % m


class Solution:

	def countBits(self, N, A):
		bitd = 0
		for i in range(32):
			count = 0
			for ele in A:
				if ele >> i & 1:
					count += 1
			bitd += count * (N - count) * 2
		return bitd % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		summ = 0
		for i in range(64):
			(cones, czeros) = (0, 0)
			for j in A:
				if j & 1 << i:
					cones += 1
				else:
					czeros += 1
			summ = summ + cones * czeros * 2
		return summ % 1000000007


class Solution:

	def countBits(self, N, A):
		i = 0
		count = 0
		while i < 32:
			setbits = 0
			for ele in A:
				if ele & 1 << i:
					setbits += 1
			count += setbits * (N - setbits) * 2
			i += 1
		return count % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		ans = 0
		for i in range(0, 32):
			count = 0
			for j in range(0, N):
				if A[j] & 1 << i:
					count += 1
			ans += count * (N - count) * 2
		return ans % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, nums):
		mask = 1
		ans = 0
		for i in range(32):
			cnt = 0
			for num in nums:
				if num & mask:
					cnt += 1
			ans += 2 * (cnt * (N - cnt))
			mask <<= 1
		return ans % int(10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		mx = max(A)
		ans = 0
		bits = len(bin(mx)[2:])
		for x in range(0, bits + 2):
			cnt = 0
			for i in range(N):
				if A[i] & 1 << x:
					cnt += 1
			ans += cnt * (N - cnt) * 2
		return ans % 1000000007


class Solution:

	def countBits(self, N, A):
		MOD = 1000000007
		res = 0
		for k in range(32):
			(ct0, ct1) = (0, 0)
			for i in range(N):
				if A[i] & 1 << k != 0:
					ct1 += 1
				else:
					ct0 += 1
			res += ct1 * ct0 % MOD
			res %= MOD
		return res * 2 % MOD


class Solution:

	def countBits(self, N, A):
		t = 0.5
		ans = 0
		for i in range(32):
			c1 = c2 = 0
			t *= 2
			for j in range(N):
				if A[j] & 1 << i:
					c1 += 1
				else:
					c2 += 1
			ans += c1 * c2 * 2
		return int(ans % 1000000007)


import numpy as np
MAX_RES = 1000000007

class Solution:

	def countBits(self, N, A):
		sum = 0
		max_numof_bits = int(np.log2(max(A)))
		for i in range(max_numof_bits + 1):
			nums_w_ith_bit_set = 0
			mask = 1 << i
			for j in range(0, N):
				if A[j] & mask:
					nums_w_ith_bit_set += 1
			nums_w_ith_bit_cleared = N - nums_w_ith_bit_set
			increment = 2 * nums_w_ith_bit_set * nums_w_ith_bit_cleared
			sum += increment
		return sum % MAX_RES


import numpy as np
MAX_RES = 1000000000 + 7

class Solution:

	def countBits(self, N, A):
		sum = 0
		max_numof_bits = int(np.log2(max(A)))
		for i in range(max_numof_bits, -1, -1):
			count = 0
			mask = 1 << i
			for j in range(0, N):
				if A[j] & mask:
					count += 1
			numbers_w_unset_ith_bit = N - count
			increment = 2 * count * numbers_w_unset_ith_bit
			sum += increment
		return sum % MAX_RES


class Solution:

	def countBits(self, n, arr):
		lis = [0] * 33
		for num in arr:
			i = num
			j = 0
			while i > 0:
				if i & 1 == 1:
					lis[j] += 1
				i //= 2
				j += 1
		ans = 0
		m = 10 ** 9 + 7
		for i in range(33):
			ans += 2 * (lis[i] * (n - lis[i]))
			ans %= m
		return ans


class Solution:

	def countBits(self, N, A):
		max_val = max(A)
		bin_max = bin(max_val)[2:]
		max_len = len(bin_max)
		countOnesZerosEachBit = [[0, 0] for i in range(max_len)]
		for num in A:
			bin_num = bin(num)[2:].zfill(max_len)
			for d in range(max_len):
				if bin_num[max_len - d - 1] == '1':
					countOnesZerosEachBit[max_len - d - 1][1] += 1
				else:
					countOnesZerosEachBit[max_len - d - 1][0] += 1
		result = 0
		for pair in countOnesZerosEachBit:
			result += pair[0] * pair[1]
		return result * 2 % (10 ** 9 + 7)


MOD = int(1000000000.0 + 7)

class Solution:

	def countBits(self, N, A):
		ans = 0
		for i in range(31, -1, -1):
			setbits = 0
			for j in A:
				if j & 1 << i:
					setbits += 1
			ans += 2 * setbits * (N - setbits)
			ans %= MOD
		return ans


class Solution:

	def f(self, n):
		s = 0
		for i in range(32):
			if n & 1 == 1:
				s += 1
			n >>= 1
		return s

	def countBits(self, N, A):
		s = 0
		MAX = 1000000007
		for i in range(32):
			c = 0
			for j in range(N):
				if A[j] & 1 << i != 0:
					c += 1
			s = (s + c * (N - c) * 2) % MAX
		return s


class Solution:

	def countBits(self, N, A):
		ans = 0
		mod = 10 ** 9 + 7
		for i in range(32):
			one = 0
			zero = 0
			for j in range(N):
				if A[j] & 1 << i:
					one += 1
				else:
					zero += 1
			ans = (ans + 2 * one * zero) % mod
		return ans


class Solution:

	def countBits(self, N, A):
		ans = 0
		for mask in range(31):
			ones = 0
			zeros = 0
			for i in range(N):
				if A[i] & 1 << mask:
					ones += 1
				else:
					zeros += 1
			ans = ans + 2 * (ones * zeros)
		return ans % 1000000007


class Solution:

	def countBits(self, N, A):
		diff = 0
		for i in range(32):
			count = 0
			for j in A:
				if j & 1 << i:
					count += 1
			rembits = N - count
			diff += rembits * count * 2
		return diff % 1000000007


class Solution:

	def countBits(self, N, A):
		has = {}
		for i in range(31):
			has[i] = 0
			for j in range(N):
				if A[j] > 0:
					has[i] += A[j] % 2
					A[j] //= 2
		res = 0
		for i in has:
			res += has[i] * (N - has[i])
		return 2 * res % (10 ** 9 + 7)


class Solution:

	def countBits(self, n, x):
		bits = 32
		z = [0 for i in range(32)]
		for i in x:
			s = bin(i)[2:].zfill(32)
			for j in range(32):
				if s[j] == '1':
					z[j] += 1
		ans = 0
		mo = 10 ** 9 + 7
		for i in x:
			s = bin(i)[2:].zfill(32)
			for j in range(32):
				if s[j] == '1':
					ans = (ans + n - z[j]) % mo
				else:
					ans = (ans + z[j]) % mo
		return ans % mo


class Solution:

	def countBits(self, N, A):
		mask = 1
		result = 0
		for _ in range(32):
			count_with_bit_set = 0
			for x in A:
				if x & mask:
					count_with_bit_set += 1
			result += count_with_bit_set * (N - count_with_bit_set) * 2
			mask <<= 1
		return result % (int(1000000000.0) + 7)


class Solution:

	def countBits(self, N, A):
		num_ones = [0] * 31
		for ele in A:
			i = 0
			while ele:
				if ele & 1:
					num_ones[i] += 1
				i += 1
				ele = ele >> 1
		res = 0
		for ele in num_ones:
			res += ele * (N - ele) % (1000000000.0 + 7)
		return int(res * 2 % (1000000000.0 + 7))


class Solution:

	def countBits(self, N, A):
		ans = 0
		maxVal = pow(10, 9) + 7
		for i in range(32):
			count = 0
			for num in A:
				if num & 1 << i:
					count += 1
			ans += 2 * count * (N - count)
		return ans % maxVal
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


class Solution:

	def countBits(self, N, A):
		maxi = 1000000000.0 + 7
		ans = 0
		for i in range(0, 32):
			cnt = 0
			for j in range(N):
				if A[j] & 1 << i != 0:
					cnt += 1
			ans = (ans + cnt * (N - cnt) * 2) % maxi
		return int(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


class Solution:

	def countBits(self, N, A):
		diff = 0
		p = 10 ** 9 + 7
		for i in range(32):
			c = 0
			for j in range(N):
				if 1 << i & A[j]:
					c += 1
			diff += c * (N - c) * 2
		return diff % p
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


from collections import defaultdict
import math

class Solution:

	def countBits(self, N, A):
		msb = int(math.log2(max(A)))
		ans = 0
		m = 10 ** 9 + 7
		for i in range(msb, -1, -1):
			c = 0
			for j in A:
				if j & 1 << i:
					c += 1
			ans += 2 * (c * (N - c)) % m
		return ans % m
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


from collections import defaultdict

class Solution:

	def countBits(self, N, A):
		d = defaultdict(int)
		ans = 0
		m = 10 ** 9 + 7
		for i in A:
			b = 0
			while i:
				if i & 1:
					d[b] += 1
				i >>= 1
				b += 1
		for (k, v) in d.items():
			ans += 2 * (v * (N - v)) % m
		return ans % m
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


class Solution:

	def countBits(self, n, arr):
		ans = 0
		for i in range(0, 32):
			count = 0
			for j in range(0, n):
				if arr[j] & 1 << i:
					count += 1
			ans += count * (n - count) * 2 % 1000000007
		return ans % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		A = input().split()
		for it in range(N):
			A[it] = int(A[it])
		ob = Solution()
		print(ob.countBits(N, A))


MOD = 10 ** 9 + 7

class Solution:

	def countBits(self, N, A):

		def _calc(bit):
			c1 = c0 = 0
			for v in A:
				if v & bit:
					c1 += 1
				else:
					c0 += 1
			return c1 * c0 * 2
		ans = 0
		maxv = max(A)
		bit = 1
		while bit <= maxv:
			ans = (ans + _calc(bit)) % MOD
			bit <<= 1
		return ans


class Solution:

	def countBits(self, N, A):
		ans = 0
		for i in range(31, -1, -1):
			count_1 = 0
			count_0 = 0
			for ele in A:
				if ele & 1 << i:
					count_1 += 1
				else:
					count_0 += 1
			ans = ans + count_1 * count_0
		return ans * 2 % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		ans = 0
		for i in range(31, -1, -1):
			count_1 = 0
			count_0 = 0
			for ele in A:
				binary_no = bin(ele)[2:]
				l = len(binary_no)
				zero_str = ''
				for _ in range(32 - l):
					zero_str = zero_str + '0'
				final_bno = zero_str + binary_no
				if final_bno[i] == '1':
					count_1 += 1
				else:
					count_0 += 1
			ans = ans + count_1 * count_0
		return ans * 2 % (10 ** 9 + 7)


import math

class Solution:

	def count_difference(self, N, A, i):
		mask = 1 << i
		count_ones = 0
		for number in A:
			count_ones += number & mask > 0
		return count_ones * (N - count_ones) % (1000000000.0 + 7)

	def countBits(self, N, A):
		count = 0
		num_of_bits = math.floor(math.log(max(A), 2)) + 1
		for i in range(num_of_bits):
			count = (count + self.count_difference(N, A, i)) % (1000000000.0 + 7)
		return int(2 * count % (1000000000.0 + 7))


from itertools import combinations

class Solution:

	def countBits(self, N, A):
		s = 0
		mod = 10 ** 9 + 7
		for i in range(0, 32):
			count = 0
			for j in range(0, N):
				if A[j] & 1 << i:
					count += 1
			s += count * (N - count) * 2 % mod
			if s >= mod:
				s -= mod
		return s


class Solution:

	def countBits(self, N, A):
		c = 0
		for i in range(32):
			t = 0
			for j in A:
				t += 1 if j & 1 << i else 0
			c += t * (N - t) * 2
		return c % 1000000007


class Solution:

	def countBits(self, n, l):
		t = [0 for _ in range(32)]
		for i in l:
			x = 0
			while i > 0:
				if i % 2 == 1:
					t[x] += 1
				x += 1
				i = i // 2
		ans = 0
		for i in t:
			ans = (ans + 2 * i * (n - i)) % 1000000007
		return ans


class Solution:

	def countBits(self, N, A):
		sum = 0
		n = len(A)
		x = 1000000007
		for i in range(0, 32):
			count = 0
			for j in range(0, n):
				if A[j] & 1 << i:
					count += 1
			sum += 2 * count * (n - count)
		return sum % x


class Solution:

	def countBits(self, N, A):
		mod = 10 ** 9 + 7
		res = 0
		for i in range(32):
			cur = 1 << i
			ones = 0
			for j in A:
				if j & cur:
					ones += 1
			res += 2 * ones * (N - ones)
		return res % mod


from math import log2

class Solution:

	def countBits(self, N, A):
		m = int(log2(max(A)))
		mod = 1000000000.0 + 7
		r = 0
		for i in range(m + 1):
			c = 0
			for j in range(N):
				if A[j] & 1 << i != 0:
					c += 1
			r = (r + 2 * c * (N - c)) % mod
		return int(r)


class Solution:

	def countBits(self, n, arr):
		l = [0 for i in range(32)]
		for val in arr:
			for i in range(32):
				if val & 1 << i:
					l[i] += 1
		ans = 0
		for i in range(32):
			ans += 2 * (n - l[i]) * l[i] % (10 ** 9 + 7)
		return ans % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		res = 0
		for i in range(32):
			m = 0
			for j in A:
				if j & 1 << i == 1 << i:
					m += 1
			res += m * (N - m) * 2
		return res % 1000000007


class Solution:

	def countBits(self, N, A):
		sum = 0
		for i in range(32):
			count1 = 0
			for j in range(N):
				if A[j] & 1 << i:
					count1 += 1
			count0 = N - count1
			sum += 2 * count0 * count1
		return sum % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		ans = 0
		bit1s = [0] * 32
		for i in range(N):
			j = 0
			k = j
			while A[i] > 0:
				bit1s[k] += A[i] & 1
				A[i] = A[i] >> 1
				k = k + 1
		for i in range(32):
			ans = (ans + bit1s[i] * (N - bit1s[i]) * 2) % 1000000007
		return ans


class Solution:

	def countBits(self, N, A):
		res = 0
		for i in range(0, 32):
			count = 0
			for val in A:
				if val & 1 << i != 0:
					count += 1
			off = N - count
			diff = count * off * 2
			res += diff
		return res % 1000000007


class Solution:

	def countBits(self, N, A):
		max_ele = max(A)
		pos = 0
		while max_ele > 0:
			max_ele = max_ele >> 1
			pos += 1
		final_count = 0
		p = 10 ** 9 + 7
		for i in range(pos):
			zero_count = 0
			mask = 1 << i
			for ele in A:
				if ele & mask == 0:
					zero_count += 1
			final_count = (final_count + 2 * zero_count * (N - zero_count)) % p
		return final_count


class Solution:

	def countBits(self, N, A):
		ans = 0
		mod = 10 ** 9 + 7
		for i in range(32):
			mask = 1 << i
			ones = 0
			zeros = 0
			for val in A:
				if val & mask > 0:
					ones += 1
				else:
					zeros += 1
			total = ones * zeros % mod
			total = (total + total) % mod
			ans = (ans + total) % mod
		return ans


from itertools import combinations

class Solution:

	def bin_diffrence(self, pair):
		bin_diff_bet_pair = 0
		a = min(pair)
		b = max(pair)
		bin_a = bin(a)[2:]
		bin_b = bin(b)[2:]
		diff_bet_len = len(bin_b) - len(bin_a)
		bin_a = '0' * diff_bet_len + bin_a
		i = len(bin_a) - 1
		for i in range(len(bin_b)):
			if bin_a[i] != bin_b[i]:
				bin_diff_bet_pair += 1
			i -= 1
		return bin_diff_bet_pair

	def countBits(self, N, a):
		modulo_number = 10 ** 9 + 7
		full_diff = 0
		for i in range(32):
			set_bits = 0
			for elem in a:
				if elem & 1 << i:
					set_bits += 1
			unset_bits = N - set_bits
			full_diff += 2 * set_bits * unset_bits
		return full_diff % modulo_number


class Solution:

	def countBits(self, N, A):
		ans = 0
		for bit in range(32):
			count = 0
			for (i, el) in enumerate(A):
				if el & 1 << bit:
					ans += (i - count) % (10 ** 9 + 7)
					count += 1
				else:
					ans += count % (10 ** 9 + 7)
				ans = ans % (10 ** 9 + 7)
		return ans * 2 % (10 ** 9 + 7)


class Solution:

	def countBits(self, N, A):
		res = 0
		MODULO = pow(10, 9) + 7
		for i in range(32):
			count = 0
			for j in range(N):
				if A[j] & 1 << i:
					count += 1
			res += count * (N - count) * 2 % MODULO
		return res % MODULO