Product of XOR of All Good Pairs
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
1Example 1
Example 1: (1^2) * (1^3) * (1^7) * (2^3) * (2^7) * (3^7) = 720
2Example 2
Example 2: (4^3) * (4^7) * (3^7) = 84
Constraints
Limits and guarantees your solution can rely on.
See above