Chef has a sequence of N$N$ integers A1,A2,...,AN$A_1, A_2, ..., A_N$. 
Chef thinks that a triplet of integers (i,j,k)$(i,j,k)$ is good if 1≤i<j<k≤N$1 \leq i < j < k \leq N$ and P$P$ in the following expression contains an odd number of ones in its binary representation:
P=[Ai<<(⌊log2(Aj)⌋+⌊log2(Ak)⌋+2)]+[Aj<<(⌊log2(Ak)⌋+1)]+Ak$P = [ A_i<< (  \lfloor \log_2(A_j) \rfloor + \lfloor \log_2(A_k) \rfloor + 2 ) ] + [A_j << ( \lfloor \log_2(A_k) \rfloor + 1) ] + A_k$
The <<$<<$ operator is called left shift, x<<y$x << y$  is defined as x⋅2y$x \cdot 2^y$.
Help the Chef finding the total number of good triplets modulo 109+7$10^9 + 7$.

-----Input:-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains a single integer N$N$. 
- The second line of each test case contains N$N$ space-separated integers A1,A2,...,AN$A_1, A_2, ..., A_N$.

-----Output:-----
For each test case, print a single line containing one integer, the number of good triplets modulo 109+7$10^9+7$.

-----Constraints:-----
- 1≤T≤103$1 \leq T \leq 10^3$
- 1≤N≤105$1\leq N \leq 10^5$
- 1≤Ai≤109$1 \leq A_i \leq 10^9$
- The sum of N$N$ over all testcases is less than 106$10^6$

-----Sample Input:-----
1
4
1 1 2 3

-----Sample Output:-----
1

Difficulty: interview

Starter code:

Solutions:
from math import *
t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(d) for d in input().split()]
    odd,even = 0,0
    for i in range(n):
     if bin(a[i]).count("1")%2 == 1:
      odd += 1
     else:
      even +=1
    total = 0
    if odd >= 3 and even >= 2:
     total += (odd*(odd-1)*(odd-2))//6
     total += odd*(even*(even-1))//2
    elif odd >= 3 and even < 2:
     total +=  (odd*(odd-1)*(odd-2))//6
    elif 0<odd < 3 and even >= 2:
     total +=  odd*(even*(even-1))//2
 
    print(total%(10**9+7))

from math import *
t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(d) for d in input().split()]
    odd,even = 0,0
    for i in range(n):
     if bin(a[i]).count("1")%2 == 1:
      odd += 1
     else:
      even +=1
    total = 0
    if odd >= 3 and even >= 2:
     total += (odd*(odd-1)*(odd-2))//6
     total += odd*(even*(even-1))//2
    elif odd >= 3 and even < 2:
     total +=  (odd*(odd-1)*(odd-2))//6
    elif 0<odd < 3 and even >= 2:
     total +=  odd*(even*(even-1))//2
 
    print(total%(10**9+7))

# cook your dish here
def f(n):
    c=0
    while(n):
     n=n&(n-1)
     c^=1
    return c 

mod=10**9+7
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    od,ev=0,0
    for i in l:
     if(f(i)):
      od+=1
     else:
      ev+=1
    p,q=0,0
    if(od>=3):
     p=od*(od-1)*(od-2)
     p=p//6
    if(ev>=2 and od>0):
     q=ev*(ev-1)
     q=q>>1
     q=q*od

# cook your dish here
def f(n):
    c=0
    while(n):
     n=n&(n-1)
     c^=1
    return c 

mod=10**9+7
for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    od,ev=0,0
    for i in l:
     if(f(i)):
      od+=1
     else:
      ev+=1
    p,q=0,0
    if(od>=3):
     p=od*(od-1)*(od-2)
     p=p//6
    if(ev>=2 and od>0):
     q=ev*(ev-1)
     q=q>>1
     q=q*od