Chef has invited Alice for his birthday party. Now, Alice is thinking about what to give Chef as a present. She should obviously choose a sequence ― what could possibly be a better birthday gift than a sequence!
After some thinking, Alice chose a sequence of integers $A_1, A_2, \ldots, A_N$. However, she does not want to simply give this sequence to Chef. Instead, she decided to give Chef a sequence $B_1, B_2, \ldots, B_N$, where $B_i = \bigvee_{j=1}^i A_j$ for each valid $i$ and $\bigvee$ denotes the bitwise OR operation. Chef can try to generate a sequence $A$ from $B$, but there could be more than one such possible sequence.
Now, Alice is wondering how many sequences $A$ correspond to the given sequence $B$. Since this number could be very large, compute it modulo $10^9 + 7$. Note that it is not guaranteed that the given sequence $B$ was generated from some sequence $A$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $B_1, B_2, \ldots, B_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of possible sequences $A$ modulo $10^9 + 7$.

-----Constraints-----
- $1 \le T \le 25$
- $1 \le N \le 5 \cdot 10^4$
- $0 \le B_i < 2^{30}$ for each valid $i$

-----Example Input-----
2
2
2 3
4
2 6 7 7

-----Example Output-----
2
64

-----Explanation-----
Example case 1: There are two possible options for $A$: $(2, 1)$ and $(2, 3)$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Combinatorics


Solutions:
import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	B = list(map(int, sys.stdin.readline().split()))
	k = 0
	for i in range(len(B) - 1):
		if bin(B[i] & ~B[i + 1]).count('1') > 0:
			k = -1
			break
		k += bin(B[i] & B[i + 1]).count('1')
	if k == -1:
		print(0)
	else:
		print(2 ** k % 1000000007)


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 10 ** 9 + 7
	f = 1
	p = 0
	for i in range(1, n):
		x = a[i - 1] & a[i]
		if x == a[i - 1]:
			p += bin(a[i - 1]).count('1')
		else:
			f = 0
			break
	if f == 0:
		print(f % m)
	else:
		print(2 ** p % m)


import math
T = int(input())
for i in range(T):
	n = int(input())
	ar = [int(x) for x in input().split()]
	mod = 10 ** 9 + 7
	ans = 1
	c = 0
	for i in range(1, n):
		x = ar[i] & ar[i - 1]
		if x == ar[i - 1]:
			c += bin(ar[i - 1]).count('1')
		else:
			ans = 0
			break
	if ans == 0:
		print(ans % mod)
	else:
		print(2 ** c % mod)


const = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	ans = 1
	Bi = list(map(int, input().split()))
	for i in range(N - 1):
		if str(bin(Bi[i])).count('1') - str(bin(Bi[i + 1])).count('1') > 0:
			ans = 0
			break
		ans = ans % const * pow(2, str(bin(Bi[i])).count('1')) % const % const
	print(ans)


def get_num_of_ones(x):
	c = 0
	while x:
		x &= x - 1
		c += 1
	return c
mod = 10 ** 9 + 7
twopow = {x: pow(2, x) % mod for x in range(35)}
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	ones_in_prev = 0
	ones_in_current = 0
	ans = 1
	flag = True
	ones_in_current = get_num_of_ones(b[0])
	ones_in_prev = ones_in_current
	for i in range(1, n):
		ans *= twopow[ones_in_prev]
		ans %= mod
		ones_in_current = get_num_of_ones(b[i])
		ones_in_prev = ones_in_current
		if b[i] < b[i - 1]:
			flag = False
			break
	if flag:
		print(ans % mod)
	else:
		print(0)


def no_of_ones(x):
	exp = 0
	for ele in bin(x)[2:]:
		if ele == '1':
			exp += 1
	return exp
for i in range(int(input())):
	size = int(input())
	arr = [int(i) for i in input().split()]
	result = 0
	ans = 1
	for i in range(size - 1):
		result += no_of_ones(arr[i])
	poss = True
	for i in range(size - 1):
		if arr[i] & arr[i + 1] != arr[i]:
			poss = False
			break
	print(pow(2, result, 1000000007) if poss else 0)


from sys import stdin, stdout

def result(arr):
	M = 10 ** 9 + 7
	for i in range(n - 1):
		if arr[i] & arr[i + 1] != arr[i]:
			return 0
	c = 0
	for i in range(n):
		c += bin(arr[i]).count('1')
	c -= bin(arr[-1]).count('1')
	ans = 2 ** (c % M) % M
	return ans
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	print(result(arr))


m = 10 ** 9
m += 7

def calc(i):
	a = 0
	while i > 0:
		q = i % 2
		a += q
		i = i // 2
	return a
for tst in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 1
	for k in range(n - 1):
		if a[k] & a[k + 1] == a[k]:
			kk = calc(a[k])
			ans = ans * 2 ** kk % m
		else:
			ans = 0
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list([int(j) for j in input().split()])
	count = 1
	res = 1
	if n > 1:
		for j in range(n - 1):
			if a[j + 1] | a[j] > a[j + 1]:
				res = 0
				break
			x = str(bin(a[j + 1])[2:]).count('1')
			y = str(bin(a[j + 1] - a[j])[2:]).count('1')
			count *= pow(2, x - y, 1000000007)
			count %= 1000000007
	if res == 0:
		print(0 % 1000000007)
	else:
		print(count % 1000000007)


for _ in range(int(input())):
	N = int(input())
	array = list(map(int, input().split()))
	ans = 1
	Binary = [bin(array[0]).count('1')]
	for i in range(1, N):
		T = array[i]
		a = array[i - 1]
		Binary.append(bin(array[i]).count('1'))
		test = bin(T & a).count('1')
		if Binary[i - 1] > test:
			ans = 0
			break
		ans = ans * (2 ** test % (10 ** 9 + 7)) % (10 ** 9 + 7)
	print(ans)


t = int(input())
while t > 0:
	N = int(input())
	B = list(map(int, input().split()))
	k = 0
	for i in range(len(B) - 1):
		if bin(B[i] & ~B[i + 1]).count('1') > 0:
			k = -1
			break
		k += bin(B[i] & B[i + 1]).count('1')
	if k == -1:
		print(0)
	else:
		k = 2 ** k % 1000000007
		print(k)
	t -= 1


m = pow(10, 9) + 7
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = 1
	for i in range(n - 1):
		if l[i] <= l[i + 1] and l[i] & l[i + 1] == l[i]:
			y = bin(l[i]).count('1')
			t = t * pow(2, y, m) % m
		else:
			t = 0
			break
	print(t % m)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	a = 1
	for i in range(1, n):
		p = l[i - 1] & l[i]
		if p != l[i - 1]:
			a = 0
			break
		else:
			c += bin(p).count('1')
	if a == 0:
		print(0)
	else:
		print(2 ** c % (10 ** 9 + 7))


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	k = 0
	p = int(1000000000.0 + 7)
	for i in range(n - 1):
		if bin(x[i] & ~x[i + 1]).count('1') > 0:
			k = -1
			break
		else:
			k += bin(x[i]).count('1')
	if k == -1:
		print(0)
	else:
		print(pow(2, k, p))


from sys import stdin

def power(b, p, m):
	if p == 0:
		return 1
	else:
		x = power(b, p // 2, m) % m
		x = x * x % m
		if p % 2 == 0:
			return x % m
		else:
			return x * b % m
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	s = 0
	flag = False
	for i in range(1, n):
		if bin(arr[i - 1]).count('1') > bin(arr[i]).count('1'):
			print('0')
			flag = True
			break
		s += bin(arr[i - 1]).count('1')
	if not flag:
		print(power(2, s, 1000000007))


import sys

def finp():
	return sys.stdin.readline()

def fop(s):
	return sys.stdout.write(str(s) + '\n')

def fintinp():
	return int(sys.stdin.readline())

def flistintinp():
	return list(map(int, finp().split()))

def op(s):
	return s

def inp():
	return input()

def intop(s):
	return int(s)

def intinp():
	return int(input())

def listintinp():
	return list(map(int, inp().split()))

def listinp():
	return list(map(str, inp().split()))
import math
primelists = []
maxprecomprimeval = 100001
from math import ceil, sqrt
mysievelists = [i for i in range(maxprecomprimeval)]

def primeprecomputer():
	for i in range(2, math.ceil(math.sqrt(maxprecomprimeval))):
		if mysievelists[i] == i:
			for j in range(i * i, maxprecomprimeval, i):
				if mysievelists[j] == j:
					mysievelists[j] = i
	for i in range(2, maxprecomprimeval):
		if mysievelists[i] == i:
			primelists.append(mysievelists[i])
	return primelists
from bisect import bisect_right, bisect_left

def bisectright(lists, nbr):
	return bisect_right(lists, nbr)

def bisectleft(lists, nbr):
	return bisect_left(lists, nbr)
MOD = 100000007
mpflists = []

def mpf(n):
	k = 0
	primeprecomputer()
	while n != 1:
		print(mysievelists[n])
		mpflists.append(mysievelists[n])
		n //= mysievelists[n]
		k += 1
	return mpflists
for __ in range(intinp()):
	n = intinp()
	lists = flistintinp()
	v = 0
	set = 0
	for i in range(1, n):
		if lists[i] < lists[i - 1]:
			set = 1
			break
		val = bin(lists[i] & lists[i - 1])
		v = v + val.count('1')
	if set == 1:
		print('0')
	else:
		print(pow(2, v, 10 ** 9 + 7))


t = int(input())
mod = pow(10, 9) + 7
while t > 0:
	t -= 1
	n = int(input())
	b = [int(x) for x in input().split()]
	bprev = b[0]
	ans = 1
	for i in range(1, n):
		if bin(~b[i] & b[i - 1]).count('1'):
			ans = 0
			break
		ans += bin(b[i] & b[i - 1]).count('1')
	if ans == 0:
		print(ans)
	else:
		ans -= 1
		print(2 ** ans % 1000000007)


import sys
sys.setrecursionlimit(10 ** 3)

def fast_expo(n):
	mod = 10 ** 9 + 7
	if n == 1:
		return 2
	x = fast_expo(n // 2) % mod
	if n % 2 == 0:
		return x * x % (10 ** 9 + 7)
	else:
		return x * x * 2 % (10 ** 9 + 7)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 0
	c = 0
	flag = 0
	mod = 10 ** 9 + 7
	for i in range(len(l) - 1):
		t_1 = list(bin(l[i])[2:]).count('1')
		if c <= t_1:
			c = t_1
		else:
			flag = 1
		p += t_1
	if flag == 1:
		print(0)
		continue
	t_2 = fast_expo(p) % mod
	print(t_2)


def solve(lis, n):
	cnt = 0
	for i in range(1, n):
		val = lis[i] & lis[i - 1]
		if val != lis[i - 1]:
			return -1
		for i in range(32):
			if 1 << i & val > 0:
				cnt += 1
	return 2 ** cnt % mod
for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	mod = int(1000000000.0) + 7
	ans = solve(lis, n)
	print(0 if ans == -1 else ans)


M = 1000000007
T = int(input())
for _ in range(T):
	n = int(input())
	l = [int(i) for i in input().split()]
	count1 = 0
	for i in range(1, n):
		if l[i - 1] & l[i] != l[i - 1]:
			count1 = 0
			break
		else:
			count1 += bin(l[i - 1] & l[i]).count('1')
	if count1 == 0:
		print(count1)
	else:
		print(2 ** count1 % M)


def cb(n):
	c = 0
	while n:
		if n & 1:
			c += 1
		n >>= 1
	return c
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	d = 0
	for i in range(n - 1):
		if l[i] & l[i + 1] != l[i]:
			print(0)
			d = 1
			break
	if d == 1:
		continue
	c = 0
	for i in l:
		c += cb(i)
	c -= cb(l[n - 1])
	print(2 ** c % 1000000007)


def countSetBits(n):
	total = 0
	while n:
		total += n & 1
		n = n >> 1
	return total

def totalWays(bArr, n):
	valid = True
	for i in range(1, len(bArr)):
		if bArr[i] & bArr[i - 1] != bArr[i - 1]:
			valid = False
	if not valid:
		return 0
	mod = int(1000000000.0 + 7)
	total_ways = 1
	for i in range(1, len(bArr)):
		setbits = countSetBits(bArr[i - 1])
		total_ways *= pow(2, setbits, mod)
		total_ways %= mod
	return total_ways % mod

def main():
	t = int(input())
	while t:
		n = int(input())
		bArr = [int(x) for x in input().split()]
		print(totalWays(bArr, n))
		t -= 1
main()


import sys
m = 1000000000.0 + 7

def countSetBits(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 1
	flag = 0
	for i in range(n - 1):
		if nums[i] > nums[i + 1]:
			flag = 1
			break
		ans = ans % m * pow(2, countSetBits(nums[i])) % m % m
	if flag:
		print(0)
	else:
		print(int(ans))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	setb = lambda x: bin(x).count('1')
	ans = 1
	mult = []
	for i in range(1, N):
		if arr[i] & arr[i - 1] != arr[i - 1]:
			mult.clear()
			break
		mult.append(setb(arr[i] & arr[i - 1]))
	ans = pow(2, sum(mult), mod)
	if not mult:
		print(0)
	else:
		print(ans)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	f = 0
	for i in range(1, n):
		if l[i] < l[i - 1]:
			f = 1
			break
		x = bin(l[i] & l[i - 1])
		count = count + x.count('1')
	if f:
		print('0')
		continue
	print(2 ** count % M)


import sys
sys.setrecursionlimit(10 ** 3)
import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 0
	c = 0
	flag = 0
	mod = 10 ** 9 + 7
	for i in range(1, len(l)):
		if l[i - 1] > l[i]:
			flag = 1
			break
		p += list(bin(l[i] & l[i - 1])[2:]).count('1')
	if flag == 1:
		print(0)
		continue
	t_2 = pow(2, p, mod)
	print(t_2)


import sys
t = int(sys.stdin.readline())
while t:
	t -= 1
	count = 0
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	for i in range(len(arr) - 1):
		if bin(arr[i] & arr[i + 1]) != bin(arr[i]):
			count = -1
			break
		count += bin(arr[i] & arr[i + 1]).count('1')
	if count == -1:
		print(0)
	else:
		print(2 ** count % 1000000007)


import sys
readline = lambda : map(int, sys.stdin.readline().split(' '))
(T,) = readline()
for _ in range(T):
	(N,) = readline()
	B = list(readline())
	A0 = B[0]
	B1 = None
	setbits = 0
	no = False
	for j in range(1, N):
		B1 = B[j]
		if A0 & ~B1 > 0:
			print(0)
			no = True
			break
		else:
			setbits += bin(A0 & B1).count('1')
		A0 = B[j]
	if no:
		pass
	else:
		print((1 << setbits) % 1000000007)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	count = 0
	flag = 0
	for i in range(1, n):
		if b[i] < b[i - 1]:
			flag = 1
			break
		x = bin(b[i] & b[i - 1])
		count = count + x.count('1')
	if flag == 1:
		print('0')
	else:
		print(pow(2, count, 10 ** 9 + 7))


m = 1000000007
for t in range(int(input())):
	n = int(input())
	B = list(map(int, input().split()))
	if B != sorted(B):
		print(0)
	else:
		freq = [B[i] & B[i + 1] for i in range(n - 1)]
		p = 0
		for b in freq:
			b = bin(b)
			p += b.count('1')
		print(pow(2, p, m))


t = int(input())
for _ in range(t):
	n = int(input())
	falg = 1
	s = [int(x) for x in input().split()]
	sum = 0
	for i in range(1, len(s)):
		if s[i - 1] & s[i] != s[i - 1]:
			falg = 0
			break
		else:
			sum += bin(s[i - 1] & s[i]).count('1')
	if falg != 0:
		print(pow(2, sum, 1000000007))
	else:
		print(0)


m = 10 ** 9 + 7

def cs(n, count):
	while n:
		count += n & 1
		n >>= 1
	return count
for _ in range(int(input())):
	(n, b, a) = (int(input()), list(map(int, input().split())), 1)
	for i in range(1, n):
		if b[i] & b[i - 1] == b[i - 1]:
			a = a * int(pow(2, cs(b[i - 1], 0))) % m
		else:
			a = 0
			break
	print(a)


def solve(n, b):
	for i in range(n - 1):
		if b[i] & b[i + 1] != b[i]:
			print(0)
			return
	x = 0
	for i in range(n - 1):
		x += bin(b[i]).count('1')
	print(pow(2, x, mod))
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	solve(n, b)


def solve(n, b):
	for i in range(n - 1):
		if b[i] & b[i + 1] != b[i]:
			print(0)
			return
	x = 0
	for i in range(n - 1):
		x += bin(b[i]).count('1')
	ans = 1
	while x:
		if x > 30:
			ans *= twopow[30]
			ans %= mod
			x -= 30
		else:
			ans *= twopow[x]
			ans %= mod
			x = 0
	print(ans % mod)
mod = 10 ** 9 + 7
twopow = {x: (1 << x) % mod for x in range(35)}
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	solve(n, b)


t = int(input())
for _ in range(t):
	n = int(input())
	str1 = input().split(' ')
	a = [int(num) for num in str1]
	sum1 = 1
	M = 1000000007
	count = 0
	for i in range(0, len(a) - 1, 1):
		if bin(a[i] & ~a[i + 1]).count('1') > 0:
			count = -1
			break
		count += bin(a[i] & a[i + 1]).count('1')
	if count == -1:
		sum1 = 0
	else:
		sum1 = 2 ** count % M
	print(sum1)


def check(n):
	c = 0
	while n != 0:
		c += 1
		n = n & n - 1
	return pow(2, c)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 1
	mod = 1000000007
	f = 0
	f1 = 0
	for i in range(n - 1):
		if l[i] & l[i + 1] != l[i]:
			f1 = 1
			break
		c1 = check(l[i])
		m = m % mod * (c1 % mod) % mod
	if f1 == 1:
		print(0)
	else:
		print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	bl = list(map(int, input().split()))
	agg = 0
	flag = True
	for i in range(n - 1):
		if bl[i] ^ bl[i + 1] > bl[i + 1]:
			flag = False
			break
		temp = '{0:b}'.format(bl[i])
		agg += temp.count('1')
	if flag:
		agg = 2 ** agg
		print(agg % 1000000007)
	else:
		print(0)


import sys
f = sys.stdin
readline = lambda : map(int, f.readline().rstrip().split(' '))
(T,) = readline()
for i in range(T):
	(N,) = readline()
	B = list(readline())
	ans = 0
	impossible = False
	for i in range(len(B) - 1):
		ans += bin(B[i] & B[i + 1]).count('1')
		if bin(B[i] & ~B[i + 1]).count('1') > 0:
			impossible = True
	ans = 2 ** ans % 1000000007
	print(0 if impossible else ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	m = 1000000007
	p = 1
	flag = 0
	for j in range(n - 1):
		if b[j + 1] | b[j] > max(b[j], b[j + 1]):
			p = 0
			break
		s = bin(b[j]).count('1')
		p = p * pow(2, s, m) % m
	print(p)


m = pow(10, 9) + 7
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	f = a[0]
	for i in range(1, n):
		p = f
		q = a[i]
		g = p & q
		if g != p:
			c = 0
			break
		f = a[i]
		c = c * pow(2, bin(g)[2:].count('1')) % m
	print(c)
	t = t - 1


for i in range(int(input())):
	n = int(input())
	sum1 = 1
	l = list(map(int, input().split()))
	for i in range(1, n):
		z = l[i] & l[i - 1]
		str1 = bin(z).replace('0b', '')
		cnt1 = str1.count('1')
		if l[i] | l[i - 1] > l[i]:
			sum1 = 0
			break
		sum1 = sum1 * 2 ** cnt1
		sum1 = sum1 % 1000000007
	print(sum1)


t = int(input())
while t:
	n = int(input())
	bArr = [int(x) for x in input().split()]
	valid = True
	for i in range(1, len(bArr)):
		if bArr[i] & bArr[i - 1] != bArr[i - 1]:
			valid = False
	if not valid:
		print(0)
		t -= 1
		continue
	mod = 10 ** 9 + 7
	total_ways = 1
	for i in range(1, len(bArr)):
		setbitsCount = bin(bArr[i - 1]).count('1')
		total_ways = total_ways * pow(2, setbitsCount, mod) % mod
	print(total_ways % mod)
	t -= 1


T = int(input())
mod = 10 ** 9 + 7
for z in range(T):
	N = int(input())
	arr = [int(x) for x in input().split()]
	count = 1
	flag = False
	for i in range(1, N):
		if arr[i] | arr[i - 1] > arr[i]:
			flag = True
			break
		count_1 = bin(arr[i - 1]).count('1')
		count = count * 2 ** count_1 % mod
	if flag == True:
		print(0)
	else:
		print(count)


def bi(n):
	count = 0
	while n:
		count += 1
		n = n & n - 1
	return count
t = int(input())
for q in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	ans = 1
	mod = 10 ** 9 + 7
	end = 0
	for i in range(1, n):
		if b[i] | b[i - 1] != b[i]:
			end = 1
			print(0)
			break
		else:
			k = bi(b[i] & b[i - 1])
			ans = ans * 2 ** k % mod
	if end == 0:
		print(ans)


t = int(input())
while t > 0:
	n = int(input())
	b = list(map(int, input().split()))
	ans = 1
	for i in range(n - 1):
		if b[i] > b[i + 1]:
			ans = 0
			break
		ans = ans * (1 << bin(b[i]).count('1')) % (10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))
	t = t - 1


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def countSetBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
t = int(input())
while t:
	t -= 1
	n = int(input())
	po = 0
	a = list(map(int, input().split()))
	valid = True
	for i in range(n - 1):
		if a[i] & a[i + 1] != a[i]:
			print(0)
			valid = False
			break
	if not valid:
		continue
	for i in range(n - 1):
		po += countSetBits(a[i] & a[i + 1])
	print(power(2, po, 1000000007))


t = int(input())

def bitcount(n):
	count = 0
	while n > 0:
		count = count + 1
		n = n & n - 1
	return count

def exponent(a, b, modi):
	if b == 0:
		return 1
	elif b == 1:
		return a % modi
	else:
		r = exponent(a, b // 2, modi)
		if b % 2 == 0:
			return r * r % modi
		else:
			return r * r % modi * a % modi
while t > 0:
	n = int(input())
	x = input().split()
	count = 0
	r = -1
	old = 0
	flag = 0
	for i in range(len(x) - 1):
		old = r
		r = bitcount(int(x[i]))
		if old > r:
			flag = -1
			break
		count += r
	if flag == 0:
		modi = 1000000007
		ans = exponent(2, count, modi)
		print(ans)
	else:
		print('0')
	t -= 1


mod = 10 ** 9 + 7

def pow2(x):
	(p, n) = (1, 2)
	while x:
		if x & 1:
			p = p % mod * (n % mod) % mod
		n = n % mod * (n % mod) % mod
		x //= 2
	return p

def count_bit(val):
	bit = 0
	for i in range(30):
		if val >> i & 1:
			bit += 1
	return bit

def answer():
	val = b[0]
	po2 = 0
	for i in range(1, len(b)):
		if val > b[i]:
			return 0
		po2 += count_bit(val & b[i])
		val = b[i]
	return pow2(po2) % mod
for T in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print(answer())


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	flag = 0
	c = 0
	arr = list(map(int, stdin.readline().split()))
	for i in range(n - 1):
		if bin(arr[i] & ~arr[i + 1]).count('1') > 0:
			flag = 1
			break
		c += bin(arr[i] & arr[i + 1]).count('1')
	if flag == 1:
		print('0')
	else:
		print(2 ** c % 1000000007)


def setbit(n):
	cnt = 0
	for i in range(32):
		if n & 1 << i:
			cnt += 1
	return cnt

def power(n):
	res = 1
	a = 2
	while n > 0:
		if n & 1:
			res = res * a % 1000000007
		a = a * a % 1000000007
		n >>= 1
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(flag, bit) = (1, 0)
	for i in range(1, n):
		if arr[i - 1] & arr[i] == arr[i - 1]:
			bit += setbit(arr[i - 1])
		else:
			flag = 0
			print(0)
			break
	if flag:
		print(power(bit))


try:
	import math
	for _ in range(int(input())):
		n = int(input())
		ar = [int(x) for x in input().split()]
		mod = 10 ** 9 + 7
		ans = 1
		c = 0
		for i in range(1, n):
			x = ar[i] & ar[i - 1]
			if x == ar[i - 1]:
				c += bin(ar[i - 1]).count('1')
			else:
				ans = 0
				break
		if ans == 0:
			print(ans % mod)
		else:
			print(2 ** c % mod)
except:
	pass


mod = 1000000007
tc = int(input())
for _ in range(tc):
	n = int(input())
	b = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		if b[i - 1] & b[i] == b[i - 1]:
			count += bin(b[i - 1]).count('1')
		else:
			print(0)
			break
	else:
		ans = 2 ** count % mod
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	d = 0
	for i in range(n - 1):
		if l[i] & l[i + 1] != l[i]:
			print(0)
			d = 1
			break
	if d == 1:
		continue
	c = 0
	for i in l:
		c += bin(i)[2:].count('1')
	c -= bin(i)[2:].count('1')
	print(2 ** c % 1000000007)


t = int(input())
while t:
	t -= 1
	n = int(input())
	d = [int(i) for i in input().split()]
	a = [bin(i) for i in d]
	count = 1
	mod = 10 ** 9 + 7
	for i in range(1, n):
		c = a[i - 1].count('1')
		count *= pow(2, c, mod)
		count = count % mod
	flag = 0
	for i in range(1, n):
		if d[i - 1] | d[i] != d[i]:
			flag = 1
			print(0)
			break
	if flag == 0:
		print(count)


def countSetBits(N):
	count = 0
	while N:
		N &= N - 1
		count += 1
	return count

def main():
	T = int(input())
	mod = int(1000000000.0 + 7)
	for _ in range(T):
		N = int(input())
		B = list(map(int, input().split()))
		ans = 1
		for i in range(N):
			if i > 0 and B[i] & B[i - 1] != B[i - 1]:
				ans = 0
				break
			if i <= N - 2:
				ans = ans % mod * (pow(2, countSetBits(B[i]), mod) % mod) % mod
		print(ans)
main()


mod = 10 ** 9 + 7

def check_0(a, b):
	if a > b:
		return False
	else:
		a = bin(a)[2:]
		b = bin(b)[2:]
		a = '0' * (len(b) - len(a)) + a
		b1 = True
		for x in range(len(b)):
			if b[x] == '0':
				if a[x] == '1':
					b1 = False
					break
		return b1
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	b = True
	for i in range(1, n):
		if not check_0(arr[i - 1], arr[i]):
			b = False
			print(0)
			break
		else:
			ones = bin(arr[i] & arr[i - 1]).count('1')
			prod = 2 ** ones % mod
			ans = ans % mod * prod % mod
	if b:
		print(ans)


def c(s):
	r = 0
	while s > 0:
		if s & 1 == 1:
			r += 1
		s >>= 1
	return r
b = [1] * 40
for i in range(1, 40):
	b[i] = b[i - 1] * 2 % 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0]
	p = 1
	for i in range(1, n):
		if ~a[i] & s > 0:
			p = 0
			break
		m = c(s)
		p *= b[m]
		p %= 1000000007
		s = s | a[i]
	print(p)