I was asked this question in the online test for HackerEarth but couldn't solve it, can someone please help me understand this? Thank You.

Question

Given an array of n numbers and given two functions f(x) and g(x) where,

• f(x) = Σ(Array[x] xor Array[i]) => for i = 1 to x simplified-> f(x) = \sum_{i=1}^{x}
  if there exists a p such that 1<=p<=x-1 and (Array[p] & Array[x]) is greater that 0.

• f(x) = 0 if x = 1 or there exists no p satisfying the above condition.

• g(x) = Σ(Array[x] xor Array[i]) => for i = x to n simplified-> g(x) = \sum_{i=x}^{n}
  if there exists a p such that x+1<=p<=n and (Array[p] & Array[x]) is greater than 0.

Let A be defined as:
A = Σf(x) for => x = 1 to n simplified-> A = \sum_{x=1}^{n} f ({x})
and B is defined as:
B = Σg(x) for => x = 1 to n simplified B = \sum_{x=1}^{n} g ({x})
Find the value of (A+B)

Note: Here xor is bitwise xor operator and & is bitwise and operator.

Input

First line will contain a single integer t denoting number of test cases.

In each test case:
First line will contain n denoting number of elements in the array.
Second line will contain n denoting separated integers denoting the array.

Output

Output for each test case will be single integer denoting the value of (A+B). Since the value of A+B can be very large output it modulo (10**9+7).
Answer for each test case should come in a new line.

Input Constraints

1 <= t <= 6
1 <= n <= 10**5
0 <= Array[i] <= 10**9

Sample Input

2
3
2 1 2
3
1 2 3

Sample Output

6
9

Explanation

In first case
f(1) = 0 because x = 1
f(2) = 0 because no i exists
f(3) = 2 xor 2 + 2 xor 1 + 2 xor 2 (beacause for i = 1 Array[i] and Array[x] > 0)
= 3

Similarly,
g(1) = 3
g(2) = 0
g(3) = 0
A = 0 + 0 + 3
B = 3 + 0 + 0

(A + B)modulo 10**9+7 = 6