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)$.

Difficulty: interview

Starter code:

Solutions:
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
 while(val):
  bit+=1
  val &=(val-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())
 


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())
 


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(1e9) + 7
 ans = solve(lis, n)
 print(0 if ans == -1 else ans)

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
  cnt += bin(val).count('1')
 return (2 ** cnt) % mod

for t in range(int(input())):
 n = int(input())
 lis = list(map(int, input(). split()))
 mod = int(1e9) + 7
 ans = solve(lis, n)
 print(0 if ans == -1 else ans)

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)

import sys
sys.setrecursionlimit(10**3)
import math
"""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(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
sys.setrecursionlimit(10**3)
import math
"""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=pow(2,p,mod)
 print(t_2)

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)

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 = bin(f)[2:]
  # q = bin(a[i])[2:]
  p = f
  q = a[i]
  g = p&q
  if g != p:
   c = 0
   break
  # print(pow(2,bin(f)[2:].count("1")))
  f = a[i]
  c = c*pow(2,bin(g)[2:].count("1"))%m
  # print(c)
 print(c)
 t = t-1

# cook your dish here
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)


# cook your dish here
test=int(input());
for _ in range(test):
 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);

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 afskafshjd 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')
  continue
 print((pow(2,count,10**9+7)))# cook your dish here


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);

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)

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

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)


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)



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')
 print(str((1 << x) % mod))


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()))
 solve(n, b)


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)