An XOR operation on a list is defined here as the xor ($\oplus$) of all its elements (e.g.: $XOR(\{A,B,C\})=A\oplus B\oplus C$). 

The $\textit{XorSum}$ of set $\textbf{arr}$ is defined here as the sum of the $XOR$s of all non-empty subsets of $\textbf{arr}$ known as $ar r'$. The set $ar r'$ can be expressed as:

$\textit{Xor}\textit{Sum}(ar\textbf{r})=\sum\limits_{i=1}^{2^n-1}XOR(ar\textbf{r}_i^{\prime})=XOR(ar\textbf{r}_1^{\prime})+XOR(ar\textbf{r}_2^{\prime})+\cdots+XOR(ar\textbf{r}_{2^n-2}^{\prime})+XOB(ar\textbf{r}_{2^n-1}^{\prime})$     

For example: Given set $arr=\{n_1,n_2,n_3\}$

The set of possible non-empty subsets is: $ar r'=\{\{n_1\},\{n_2\},\{n_3\},\{n_1,n_2\},\{n_1,n_3\},\{n_2,n_3\},\{n_1,n_2,n_3\}\}$     

The $\textit{XorSum}$ of these non-empty subsets is then calculated as follows: 

$\textit{XorSum(arr)}$ = $n_1+n_2+n_3+(n_1\oplus n_2)+(n_1\oplus n_3)+(n_2\oplus n_3)+(n_1\oplus n_2\oplus n_3)$

Given a list of $n$ space-separated integers, determine and print $XorSum\%(10^9+7)$.    

For example, $arr=\{3,4\}$.  There are three possible subsets, $ar r'=\{\{3\},\{4\},\{3,4\}\}$.  The XOR of $ar r'[1]=3$, of $ar r'[2]=4$ and of $ar r[3]=3\oplus4=7$.  The XorSum is the sum of these: $3+4+7=14$ and $14\%(10^9+7)=14$.  

Note: The cardinality of powerset$\left(n\right)$ is $2^{n}$, so the set of non-empty subsets of set $\textbf{arr}$ of size $n$ contains $2^n-1$ subsets.

Function Description  

Complete the xoringNinja function in the editor below.  It should return an integer that represents the XorSum of the input array, modulo $(10^9+7)$.  

xoringNinja has the following parameter(s):  

arr: an integer array

Input Format

The first line contains an integer $\mathbf{T}$, the number of test cases.       

Each test case consists of two lines: 

-  The first line contains an integer $n$, the size of the set $\textbf{arr}$. 

-  The second line contains $n$ space-separated integers $arr\left[i\right]$.  

Constraints

$1\leq T\leq5$ 

$1\leq n\leq10^5$ 

$0\leq\textit{arr}[i]\leq10^9,\ 1\leq i\leq n$  

Output Format

For each test case, print its $XorSum\%(10^9+7)$ on a new line.  The $i^{\mbox{th}}$ line should contain the output for the $i^{\mbox{th}}$ test case.

Sample Input 0
1
3
1 2 3

Sample Output 0
12

Explanation 0

The input set, $S=\{1,2,3\}$, has $7$ possible non-empty subsets: $S'=\{\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$.

We then determine the $XOR$ of each subset in $S^{\prime}$: 

$XOR(\{1\})=1$ 

$XOR(\{2\})=2$ 

$XOR(\{3\})=3$ 

$XOR(\{1,2\})=1\oplus2=3$ 

$XOR(\{2,3\})=2\oplus3=1$ 

$XOR(\{1,3\}=1\oplus3=2$ 

$XOR(\text{{1,2,3}}=1\oplus2\oplus3=0$  

Then sum the results of the $XOR$ of each individual subset in $S^{\prime}$, resulting in $\textit{XorSum}=12$ and $12\%(10^9+7)=12$.

Sample Input 1
2
4
1 2 4 8
5
1 2 3 5 100

Sample Output 1
120
1648

Difficulty: MEDIUM_HARD
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
import sys

def poweroftwo(n):
	val = 1
	yield val
	for i in range(n):
		val *= 2
		yield val
r = sys.stdin.readline
text = r()
t = int(text)
for i in range(t):
	text = r()
	n = int(text)
	text = r()
	tmp = 0
	for num in map(int, text.split()):
		tmp |= num
	for i in range(n - 1):
		tmp *= 2
		if i % 20 == 0:
			tmp %= 1000000007
	print(tmp % 1000000007)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for b in map(lambda i: 1 << i, range(40)):
		has = any(map(lambda a: a & b, A))
		if has:
			ans += b * 2 ** (N - 1)
			ans %= 1000000007
	print(ans)


import sys
import re
rule = re.compile('\\d+')
T = int(sys.stdin.readline().rstrip('\n'))
for t in range(T):
	N = int(sys.stdin.readline().rstrip('\n'))
	A = [int(i.group()) for i in rule.finditer(sys.stdin.readline())]
	bit_or = 0
	for num in A:
		bit_or = bit_or | num
	print(2 ** (N - 1) * bit_or % (10 ** 9 + 7))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


for times in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	xs = 0
	for num in a:
		xs |= num
	print(xs * (1 << n - 1) % 1000000007)


def pow2mod(n, mod):
	result = 1
	i = 2 ** 15
	while n >= 15:
		result = result * i % mod
		n -= 15
	while n > 0:
		result = result * 2 % mod
		n -= 1
	return result

def solve(L):
	bitMask = 0
	mod = 1000000007
	for x in L:
		bitMask |= x
	a = pow2mod(len(L) - 1, mod)
	return a * bitMask % mod
t = int(input())
for i in range(0, t):
	n = int(input())
	L = [int(x) for x in input().split()]
	print(solve(L))


t = int(input())
for i in range(0, t):
	n = int(input())
	OR = 0
	temp = input()
	arr = temp.split(' ')
	for j in arr:
		OR = OR | int(j)
	print(OR * pow(2, n - 1, 1000000007) % 1000000007)


Modulo = 10 ** 9 + 7
T = int(input())
while T:
	T = T - 1
	N = int(input())
	ar = [int(i) for i in input().split()]
	SetOR = 0
	for x in ar:
		SetOR = SetOR | x
	SetOR = SetOR % Modulo
	Power2 = pow(2, N - 1, Modulo)
	res = Power2 * SetOR % Modulo
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(number) for number in input().split()]
	a_or = a[0]
	for j in range(1, len(a)):
		a_or = a_or | a[j]
	print(2 ** (n - 1) * a_or % (10 ** 9 + 7))


def my_bin(n):
	return str(bin(n))[2:]
modulo = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bits = []
	for e in a:
		b = reversed(my_bin(e))
		for (ind, bit) in enumerate(b):
			if len(bits) <= ind:
				bits.append(int(bit))
			else:
				bits[ind] = bits[ind] or int(bit)
	res = 0
	for (ind, bit) in enumerate(bits):
		res += bit * 2 ** (ind + n - 1)
		res %= modulo
	print(res)


T = int(input())
for _ in range(T):
	input()
	A = [int(i) for i in input().split(' ')]
	sum = 0
	for a in A:
		sum = (sum | a) % 1000000007
	sum = sum * 2 ** (len(A) - 1) % 1000000007
	print(sum)


t = int(input())
while t > 0:
	t -= 1
	numbers = []
	total = int(input())
	numbers = input().split()
	numbers = [int(x) for x in numbers]
	ans = numbers[0]
	for i in numbers[1:]:
		ans = ans | i
	sum = ans * pow(2, total - 1)
	sum = sum % 1000000007
	print(sum)


def sumXORsubsets(entries):
	mass_or = 0
	for entry in entries:
		mass_or |= entry
	return 2 ** (len(entries) - 1) * mass_or
modulus = 10 ** 9 + 7
num_cases = int(input())
for case in range(num_cases):
	count = int(input())
	array = [int(entry) for entry in input().split()]
	print(sumXORsubsets(array) % modulus)


def solve(X):
	s = 0
	for x in X:
		s |= x
	return s * 2 ** (len(X) - 1) % (10 ** 9 + 7)
T = int(input())
for _ in range(T):
	N = int(input())
	X = [int(_) for _ in input().split()]
	print(solve(X))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


for _ in range(int(input())):
	M = int(input()) - 1
	t = 0
	for m in input().split():
		t |= int(m)
	print((t << M) % 1000000007)


import functools, operator as op
MOD = 10 ** 9 + 7
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	x = functools.reduce(op.or_, A, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	nums = [int(x) for x in input().split()]
	total_or = 0
	for num in nums:
		total_or = total_or | num
	for i in range(n - 1):
		total_or = total_or << 1
	print(total_or % mod)


mod = 1000000007
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for a in A:
		ans |= a
	ans %= mod
	ans = ans * ((1 << N - 1) % mod) % mod
	print(ans)


import functools
t = int(input())
for _ in range(t):
	n = int(input())
	ored = functools.reduce(lambda x, y: x | y, [int(_) for _ in input().split(' ')])
	mod = 1000000007
	print(ored * 2 ** (n - 1) % mod)


nc = int(input())
MOD = 1000000007
for ca in range(nc):
	n = int(input())
	aList = [int(t) for t in input().split()]
	res = 0
	for i in range(31):
		b = 1 << i
		popu = sum((1 for a in aList if a & b != 0))
		if popu:
			v = pow(2, i + n - 1, MOD)
			res = (res + v) % MOD
	print(res)


T = int(input())
mod = 10 ** 9 + 7
for _ in range(T):
	N = int(input())
	a = [int(ns) for ns in str(input()).split()]
	ans = a[0]
	for i in range(1, N):
		ans = ans | a[i]
	print(ans * 2 ** (N - 1) % mod)


import itertools
from functools import reduce

def xor(items):
	return reduce(int.__xor__, items)

def naive_xorsum(numbers):
	acc = 0
	for i in range(1, len(numbers) + 1):
		for subset in itertools.combinations(numbers, i):
			acc = (acc + xor(subset)) % 1000000007
	return acc

def fast_xorsum(numbers):
	combined = reduce(int.__or__, numbers)
	return (combined << len(numbers) - 1) % 1000000007
cases = int(input())
for case in range(cases):
	n = int(input())
	numbers = [int(x) for x in input().split()]
	print(fast_xorsum(numbers))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


import sys
from functools import reduce
T = int(sys.stdin.readline())
while T > 0:
	T -= 1
	N = int(sys.stdin.readline())
	mask = reduce(lambda x, y: x | y, [int(x) for x in sys.stdin.readline().split()])
	print((mask << N - 1) % 1000000007)


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


from functools import reduce
special_mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	r = reduce(lambda a, b: a | b, a)
	r *= 2 ** (n - 1)
	print(r % special_mod)


from collections import defaultdict
import functools
import operator
T = int(input())
for i in range(T):
	m = defaultdict(int)
	N = int(input())
	l = map(int, input().split())
	print(2 ** (N - 1) * functools.reduce(lambda x, y: x | y, l) % (10 ** 9 + 7))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	ans = 0
	for j in range(n):
		ans = ans | int(a[j])
	ans = ans * pow(2, n - 1, 1000000007) % 1000000007
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = 0
	for i in a:
		b |= i
	print(b * 2 ** (n - 1) % 1000000007)


for tests in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	i = a[0]
	for j in a[1:]:
		i = i | j
	i = i * 2 ** (n - 1)
	print(i % (10 ** 9 + 7))


n = int(input())
for i in range(n):
	m = int(input())
	v = [int(x) for x in input().split()]
	sum = 0
	for x in v:
		sum = sum | x
	print(sum * (1 << m - 1) % 1000000007)


import functools
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	sz_arr = int(input())
	arr = [int(ele) for ele in input().split()]
	print(functools.reduce(lambda x, y: x | y, arr) * 2 ** (sz_arr - 1) % MOD)


def func():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		orr = 0
		for j in range(n):
			orr = orr | arr[j]
		res = orr * 2 ** (n - 1) % 1000000007
		print(res)
func()


from operator import or_
from functools import reduce
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(2 ** (N - 1) * reduce(or_, A) % (10 ** 9 + 7))


from functools import reduce

def mod_exp(a, b, p):
	r = 0
	if b == 0:
		return 1
	elif b % 2 == 0:
		return mod_exp(a, b / 2, p) ** 2 % p
	else:
		return a * mod_exp(a, b - 1, p) % p
p = 1000000007
T = int(input())
for t in range(0, T):
	n = int(input())
	a = [int(x) for x in input().split()]
	answer = reduce(lambda x, y: x | y, a) % p
	answer = mod_exp(2, n - 1, p) * answer % p
	print(answer)


T = int(input())
for _ in range(T):
	N = int(input())
	ar = list(map(int, input().split()))
	x = 0
	for v in ar:
		x = x | v
	print(x * 2 ** (N - 1) % (10 ** 9 + 7))


import collections
import functools
import math
import itertools
cache = {(): 0}
for i in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	vs = functools.reduce(lambda t, x: t | x, arr, 0)
	vs <<= len(arr) - 1
	print(vs % (10 ** 9 + 7))


X = 10 ** 9 + 7
T = int(input())
for t in range(0, T):
	N = int(input())
	var = input().split()
	arr = []
	ored = 0
	for i in range(0, N):
		arr.append(int(var[i]))
		ored |= arr[i]
	answer = ored * (1 << N - 1) % X
	print(answer)


MOD = 1000000007
t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	for i in range(n):
		res = (res | a[i]) % MOD
	print(res * 2 ** (n - 1) % MOD)


t = int(input())
for i in range(t):
	n = int(input())
	a = [0] * 100000
	h = 1
	a = list(map(int, input().split()))
	sum = a[0]
	for j in range(1, n):
		h = h * 2 % 1000000007
		sum = sum | a[j]
	b = sum * h % 1000000007
	print(b)


import sys
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	OR = 0
	for a in [int(X) for X in sys.stdin.readline().split()]:
		OR |= a
	print(2 ** (N - 1) * OR % 1000000007)


numOfCase = int(input())
for noc in range(numOfCase):
	_l = int(input())
	l = list(map(lambda s: int(s), input().split(' ')))
	res = pow(2, len(l) - 1) % 1000000007
	tmp = 0
	for n in l:
		tmp = tmp | n
	tmp = tmp % 1000000007
	res = res * tmp % 1000000007
	print(res)


from functools import reduce
k = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().strip().split()]
	OrA = reduce(lambda a, b: a | b, A)
	XorSum = OrA * 2 ** (n - 1)
	print(XorSum % k)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(i) for i in input().split()]
	orvalue = 0
	tot = 0
	for num in nums:
		orvalue = orvalue | num
	tot = orvalue * 2 ** (n - 1)
	print(tot % (10 ** 9 + 7))


import itertools
import functools
import operator
testcases = int(input())
for tc in range(testcases):
	count = int(input())
	digits = [int(x) for x in input().split(' ')]
	xorsum = functools.reduce(operator.or_, digits) * 2 ** (len(digits) - 1)
	print(xorsum % (10 ** 9 + 7))


import sys
import functools
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().strip().split()))
	res = functools.reduce(lambda x, y: x | y, A) * 2 ** (n - 1) % (10 ** 9 + 7)
	print(res)


testCases = int(input())
for testCase in range(testCases):
	n = int(input())
	lst = list(map(int, input().split()))
	acc = 0
	for e in lst:
		acc |= e
	print((acc << n - 1) % (10 ** 9 + 7))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


import math
t = int(input())
for case in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	or_result = 0
	for ii in range(len(arr)):
		or_result = (or_result | arr[ii]) % (1000000000 + 7)
	print(int(or_result * 2 ** (n - 1) % (1000000000 + 7)))


t = int(input())
for i in range(t):
	n = int(input())
	values = [int(x) for x in input().split()]
	result = 0
	for v in values:
		result |= v
	print(result * 2 ** (n - 1) % 1000000007)


nth = lambda x, i: x >> i & 1
M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = 0
	for j in range(32):
		(a, b) = (0, 0)
		for x in reversed(l):
			if nth(x, j) == 1:
				(a, b) = (a + b + 1, b + a)
			else:
				(a, b) = (2 * a, 2 * b + 1)
			a %= M
			b %= M
		s = (s + (a << j) % M) % M
	print(s)


def xor_sum(n, nums):
	mask = 0
	for i in nums:
		mask = (mask | i) % (10 ** 9 + 7)
	mask *= 2 ** (n - 1)
	return mask % (10 ** 9 + 7)
cases = [(int(input()), [int(i) for i in input().split()]) for j in range(int(input()))]
for case in cases:
	print(xor_sum(case[0], case[1]))


import itertools
no_cases = int(input())
results = []
for a0 in range(no_cases):
	list_size = int(input())
	test_case = input().split()
	test_case = list(map(int, test_case))
	result = 0
	for a in test_case:
		result |= a
	results.append(result * pow(2, list_size - 1) % 1000000007)
for a in results:
	print(a)


md = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	xsum = 0
	for i in range(N):
		xsum |= arr[i]
	for _ in range(N - 1):
		xsum = xsum * 2 % md
	print(xsum)


from functools import reduce

def getSubsetsOf(arr, subsets):
	if len(arr) <= 1:
		subsets.append(arr)
		return subsets
	else:
		temp = getSubsetsOf(arr[1:], subsets)
		olds = len(temp)
		for i in range(olds):
			temp.append([arr[0]] + temp[i])
		temp.append([arr[0]])
		return temp
cases = int(input().strip())
for case in range(cases):
	size = int(input().strip())
	arr = list(map(int, input().strip().split(' ')))
	num = 2 ** (size - 1) * reduce(lambda a, b: a | b, arr)
	num = num % (10 ** 9 + 7)
	print(num)


M = 1000000007
tests = int(input().strip())
for i in range(0, tests):
	n = int(input().strip())
	a = [int(x.strip()) for x in input().strip().split()]
	b0 = [0 for y in range(0, 32)]
	b1 = [0 for y in range(0, 32)]
	for k in range(0, n):
		for j in range(0, 32):
			if a[k] & 1 << j:
				tmp = b1[j]
				b1[j] = (b1[j] + 1 + b0[j]) % M
				b0[j] = (b0[j] + tmp) % M
			else:
				b1[j] = (b1[j] + b1[j]) % M
				b0[j] = (1 + b0[j] + b0[j]) % M
	cum = 0
	for j in range(0, 32):
		val = (1 << j) * b1[j] % M
		cum = (cum + val) % M
	print(cum)


from itertools import *
for _ in range(int(input())):
	n = int(input())
	a = list((int(x) for x in input().strip().split(' ')))
	l = list()
	s = 0
	for x in a:
		s = s | x
	print(s * 2 ** (n - 1) % (10 ** 9 + 7))


T = int(input())
for t in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	OR = 0
	for e in l:
		OR = OR | e
	ret = OR
	for i in range(n - 1):
		ret = ret * 2 % 1000000007
	print(ret)


mod = int(1000000000.0) + 7
t = int(input())
for k in range(t):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	sor = 0
	for i in range(n):
		sor |= a[i]
	sor = (1 << n - 1) * sor % mod
	print(sor)


T = int(input())
for T_i in range(T):
	n = int(input())
	s = [int(x) for x in input().split()]
	ans = 0
	for i in range(0, 32):
		for c in s:
			c = bin(c)[2:].zfill(32)
			if c[-i - 1] == '1':
				ans += 2 ** i * 2 ** (n - 1)
				ans %= 1000000007
				break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	m = 0
	for j in range(n):
		m = m | int(a[j])
	m *= pow(2, n - 1)
	m %= pow(10, 9) + 7
	print(m)


from operator import or_
from functools import reduce
r = 10 ** 9 + 7
n_tests = int(input())
for _ in range(n_tests):
	n = int(input())
	a = reduce(or_, map(int, input().split()), 0)
	print(a * pow(2, n - 1, r) % r)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	for a in arr:
		total |= a
	total *= pow(2, n - 1)
	total %= 1000000007
	print(total)


T = int(input())
for t in range(T):
	n = int(input())
	A = map(int, input().split())
	multiplicand = 2 ** (n - 1) % (10 ** 9 + 7)
	m = 0
	for a in A:
		m = m | a
	m = m % (10 ** 9 + 7)
	ans = multiplicand * m % (10 ** 9 + 7)
	print(ans)


import operator
import functools
import itertools
max_bin_length = 32

def sum_bin(pre_sum):
	r = []
	reminder = 0
	for i in range(max_bin_length):
		current = pre_sum[i] + reminder
		r += [current % 2]
		reminder = current >> 1
	r += map(int, bin(reminder)[-1:1:-1])
	return r

def from_bin(a):
	r = 0
	for (p, i) in enumerate(a):
		r = (r + (i << p)) % 1000000007
	return r

def counts_sets_with_active_bit(n_true, n_false):
	n_false_set = 2 ** n_false
	n_true_set = 2 ** (n_true - 1) if n_true > 0 else 0
	return n_false_set * n_true_set

def bin_array(a):
	return [bin(x)[-1:1:-1].ljust(max_bin_length, '0') for x in a]

def n_true(a, p):
	return sum((1 for s in a if s[p] == '1'))

def solve(a):
	pre_sum = [0 for _ in range(max_bin_length)]
	for i in range(max_bin_length):
		n1 = n_true(a, i)
		n0 = len(a) - n1
		pre_sum[i] = counts_sets_with_active_bit(n1, n0)
	post_sum = sum_bin(pre_sum)
	return from_bin(post_sum)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = map(int, input().split(' '))
		a = bin_array(a)
		print(solve(a))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	lst = [int(n) for n in input().split()]
	s_xor = 0
	for i in range(n):
		s_xor |= lst[i]
	pwr = 1 << n - 1
	print(pwr * s_xor % 1000000007)


from itertools import chain, combinations
from functools import reduce
import operator
import math
cases = int(input())
for i in range(cases):
	size = int(input())
	array = [int(x) for x in input().split()]
	answer = reduce(operator.or_, array)
	answer = answer * 2 ** (size - 1) % (10 ** 9 + 7)
	print(answer)


__author__ = 'siddharth'
MOD = pow(10, 9) + 7
from functools import reduce
for _ in range(int(input())):
	N = int(input())
	arr = map(int, input().split())
	orsum = reduce(lambda a, b: a | b, arr, 0)
	print(pow(2, N - 1) * orsum % MOD)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	xor_sum = 0
	for i in range(n):
		xor_sum |= arr[i]
	pwr = 1 << n - 1
	print(pwr * xor_sum % 1000000007)


from functools import reduce
t = int(input())
for _ in range(t):
	n = int(input())
	nums = map(int, input().split(' '))
	r = reduce(lambda x, y: x | y, nums)
	print(r * 2 ** (n - 1) % 1000000007)


import itertools
from functools import reduce

def findsubsets(S, m):
	return set(itertools.combinations(S, m))
for _ in range(int(input())):
	size = input()
	values = input().split(' ')
	or_sum = 0
	for v in values:
		or_sum |= int(v)
	xor_sum = pow(2, len(values) - 1) * or_sum
	print(xor_sum % (pow(10, 9) + 7))


from functools import reduce
from operator import or_
MOD = int(1000000000.0 + 7)
bit_func = lambda x: [1 if d == '1' else 0 for d in bin(x)[2:][::-1]]
for _ in range(int(input())):
	(n, ar) = (int(input()), [int(x) for x in input().split()])
	b = reduce(or_, ar, 0)
	p = pow(2, n - 1, MOD)
	print(sum((p * (1 << i) for (i, d) in enumerate(bit_func(b)) if d)) % MOD)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	accum = 0
	for x in s:
		accum = x | accum
	print((accum << n - 1) % 1000000007)


import sys
T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	temp = 0
	for element in arr:
		temp |= element
	print(temp * 2 ** (n - 1) % (10 ** 9 + 7))


T = int(input().strip())
for t in range(0, T):
	N = int(input().strip())
	A = list(map(int, input().strip().split(' ')))
	B = [bin(a)[2:] for a in A]
	mx = max(A)
	ndx = A.index(mx)
	mxlen = len(B[ndx])
	C = ['0' * (mxlen - len(b)) + b for b in B]
	s = ''
	for i in range(0, mxlen):
		b = '0'
		for c in C:
			if c[i] == '1':
				b = '1'
				break
		s += b
	bwOR = int(s, 2)
	print(2 ** (N - 1) * bwOR % (10 ** 9 + 7))


tc = int(input())
for i in range(tc):
	n = int(input())
	arr = input().split(' ')
	x = 0
	for j in arr:
		x = x | int(j)
	ans = x * 2 ** (n - 1) % (10 ** 9 + 7)
	print(ans)


M = 10 ** 9 + 7
for t in range(int(input())):
	input()
	s = list(map(int, input().split()))
	a = 0
	for i in range(32):
		if any((x & 1 << i for x in s)):
			a = (a + pow(2, len(s) - 1, M) * (1 << i)) % M
	print(a)


def mod_pow(a, b, p):
	res = 1
	cur = a
	while b:
		if b % 2:
			res = res * cur % p
		b //= 2
		cur = cur * cur % p
	return res
t = int(input())
mod = 10 ** 9 + 7
pows = []
pow2 = 1
reverses = []
for i in range(100001):
	pows.append(pow2)
	pow2 *= 2
	pow2 %= mod
	reverses.append(mod_pow(i, mod - 2, mod))
for tt in range(t):
	bits = [0] * 30
	n = int(input())
	a = list(map(int, input().split()))
	for x in a:
		for (i, bit) in enumerate(reversed(bin(x)[2:])):
			bits[i] += int(bit)
	result_bits = []
	for bit in bits:
		count = 0
		current_nCr = 1
		for i in range(1, bit + 1):
			current_nCr = current_nCr * (bit + 1 - i) * reverses[i] % mod
			if i % 2 == 0:
				continue
			count += current_nCr % mod * pows[n - bit] % mod
		result_bits.append(count % mod)
	sum = 0
	for (i, bit) in enumerate(result_bits):
		sum += bit * pows[i]
		sum %= mod
	print(sum % mod)


T = int(input())
for test_index in range(0, T):
	N = int(input())
	v = list(map(int, input().split(' ')))
	s = 0
	for x in v:
		s |= x
	s *= 2 ** (N - 1)
	s %= 10 ** 9 + 7
	print(s)


T = int(input())
for t in range(T):
	N = int(input())
	a = [int(x) for x in input().split()]
	b = 0
	for ia in a:
		b = b | ia
	b = bin(b)[:1:-1]
	s = 0
	p = 2 ** (N - 1)
	for i in range(len(b)):
		if b[i] == '1':
			s = (s + p) % 1000000007
		p *= 2
	print(s)


t = int(input())
for _ in range(t):
	input()
	nums = [int(num) for num in input().split()]
	orValue = 0
	for value in nums:
		orValue |= value
	result = (1 << len(nums) - 1) * orValue
	moduleValue = pow(10, 9) + 7
	print(result % moduleValue)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in a:
		x = x | i
	print(pow(2, n - 1, 10 ** 9 + 7) * x % (10 ** 9 + 7))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


import itertools
import functools
stopRange = 10 ** 9 + 7

def powerSetList1(iterable):
	s = list(iterable)
	return itertools.chain.from_iterable((itertools.combinations(s, r) for r in range(len(s) + 1)))

def powerSetList2(lst):
	r = [[]]
	for e in lst:
		r += [x + [e] for x in r]
	return r

def slowSolution():
	for _ in range(int(input())):
		input()
		inputSet = list(map(int, input().split()))
		xorSum = 0
		for _set in powerSetList2(inputSet):
			if len(_set) == 0:
				pass
			elif len(_set) > 1:
				xorSum += functools.reduce(lambda x, y: x ^ y, _set)
			else:
				xorSum += _set[0]
			if xorSum > stopRange:
				break
	print(xorSum % stopRange)

def fastSolution():
	for _ in range(int(input())):
		input()
		inputSet = list(map(int, input().split()))
		print(functools.reduce(lambda x, y: x | y, inputSet) * 2 ** (len(inputSet) - 1) % stopRange)
fastSolution()


MOD = 10 ** 9 + 7

def xorSum(things):
	setS = list(things)
	result = 0
	d = 0
	n = len(setS)
	while 2 ** d < MOD:
		reducedBit = False
		for i in range(n):
			num = setS[i]
			reducedBit |= num % 2 == 1
			setS[i] = setS[i] >> 1
		result = (result + 2 ** d * 2 ** (n - 1) * reducedBit) % MOD
		d += 1
	return result % MOD
testLen = int(input())
inputs = []
for i in range(testLen):
	inputLen = int(input())
	inputSet = [int(num) for num in input().split(' ')]
	inputs.append(inputSet)
outputs = [xorSum(inputSet) for inputSet in inputs]
for output in outputs:
	print(output)


t = int(input())
for loop in range(t):
	num = int(input())
	elements = []
	elements = [int(x) for x in input().strip().split(' ')]
	sum = elements[0]
	for x in elements[1:]:
		sum = sum | x
	sum = sum * 2 ** (num - 1)
	result = sum % (10 ** 9 + 7)
	print(result)


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


from functools import reduce
modValue = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	data = list(map(int, input().split()))
	print(reduce(lambda x, y: x | y, data) * 2 ** (N - 1) % modValue)


import _operator as op
import _functools as ft
bigprime = 1000000007
bbbits = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]

def main():
	tc = int(input())
	for case in range(tc):
		n = int(input())
		ex = list(map(int, input().split()))
		x = ft.reduce(op.or_, ex, 0)
		k = pow(2, n - 1, bigprime)
		print(sum((k * (1 << i) for (i, d) in enumerate(bbbits(x)) if d)) % bigprime)
main()


mod = 10 ** 9 + 7
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	tot = 0
	b = 0
	for x in A:
		b |= x
	p = pow(2, N - 1, mod)
	while b:
		if b & 1:
			tot = (tot + p) % mod
		p = p * 2 % mod
		b >>= 1
	print(tot)


from functools import reduce
for case in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	factor = 2 ** n // 2
	result = array[0] * factor
	for a in array[1:]:
		result |= a * factor
	print(result % (10 ** 9 + 7))


import itertools
T = int(input())
for test in range(T):
	n = int(input())
	S = {int(inp) for inp in input().strip().split(' ')}
	A = 0
	for s in S:
		A |= s
	answer = 0
	d = -1
	while A:
		if A & 1:
			answer += pow(2, n + d, 1000000007)
			if answer > 1000000007:
				answer -= 1000000007
		A >>= 1
		d += 1
	print(answer)


import math

def convert(bit_list):
	output = 0
	for bit in bit_list:
		output = output * 2 + bit
	return output
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	k = math.floor(math.log(max(1, max(arr))) / math.log(2)) + 1
	out = [0] * k
	for j in range(n):
		s = list(map(int, bin(arr[j])[2:].zfill(k)))
		for (r, i) in enumerate(out):
			if i == 0:
				out[r] = s[r]
	out = out + [0] * (n - 1)
	print(convert(out) % (10 ** 9 + 7))


from math import log2, ceil

def xorset(s):
	x = 0
	size = len(s)
	bits = ceil(log2(abs(max(s)) + 1))
	for i in range(bits + 1):
		num = sum((x & 1 for x in s))
		if num > 0:
			x += 2 ** (i + size - 1)
		for j in range(len(s)):
			s[j] >>= 1
	return x % (10 ** 9 + 7)
T = int(input())
for i in range(T):
	size = int(input())
	lst = [int(x) for x in input().split(' ')]
	print(xorset(lst))


import functools, operator as op, sys
MOD = 1000000007
bitfield = lambda n: [1 if d == '1' else 0 for d in bin(n)[2:][::-1]]
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	X = list(map(int, sys.stdin.readline().split()))
	x = functools.reduce(op.or_, X, 0)
	k = pow(2, N - 1, MOD)
	print(sum((k * (1 << i) for (i, d) in enumerate(bitfield(x)) if d)) % MOD)


MOD_VAL = 10 ** 9 + 7

def work(inputs):
	for current_input in inputs:
		total_nums = len(current_input)
		res = [0 for _ in range(32)]
		for num in current_input:
			for bit in range(32):
				if 1 << bit & num:
					res[bit] += 1
		final_res = 0
		for bit in range(32):
			if res[bit]:
				final_res = (final_res + 2 ** (total_nums - 1 + bit)) % MOD_VAL
		print(final_res)
inputs = []
for _ in range(int(input())):
	cnt = int(input())
	tmp = input().split()
	assert len(tmp) == cnt
	inputs.append([int(x) for x in tmp])
work(inputs)


from functools import reduce
for _ in range(int(input())):
	_ = input()
	a = [int(x) for x in input().split(' ')]
	print((reduce(lambda x, y: x | y, a) << len(a) - 1) % 1000000007)