Given an array of size N, find the product of XOR of all good pairs in the array. A pair (A[i],A[j]) is called good only when 0 <= i < j < N.
Since the product of good pairs might be too large, hence print product % 1e9+7.
Input Format
The first line of input contains T - number of test cases. The first line of each test case contains N - the size of the array.
The second line of each test case contains the N elements.
Output Format
Print the product of XOR of all good pairs in the array.
Constraints
30 points
2 <= N <= 10^3
70 points
2 <= N <= 10^5
General Constraints
1 <= T <= 10
1 <= A[i] <= 3000
Example 1:
Input: A = [1, 2, 3, 7]
Output: 720
Explanation:Example 1:
(1^2) * (1^3) * (1^7) * (2^3) * (2^7) * (3^7) = 720
Example 2:
Input: A = [4, 3, 7]
Output: 84
Explanation:Example 2:
(4^3) * (4^7) * (3^7) = 84
See above
input:
output: