Given an array A[] of N numbers. Now, you need to find and print the Summation of the bitwise OR of all possible subsets of this array.
As answer can be large, print it Modulo 109+7
Input:
The first line contains a single integer T denoting the number of test cases in a single test file.
The first line of each test case contains a number N denoting the number of elements in the given array.
The second line contains the N elements of the array.
Output:
For each test case output a single number denoting the Summation of bitwise OR of all possible subsets of the given array.
Input Constraints:
1≤T≤101≤N≤1051≤A[i]≤109
For [1, 2, 3], all possible subsets are {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
The sum of OR of these subsets are, 1 + 2 + 3 + 3 + 3 + 3 + 3 = 18.
So, the answer would be 18.
