Product of XOR of All Good Pairs

For all 0≤i<j<N, compute A[i] XOR A[j], multiply all these results together, and take the product modulo 1000000007. Each test case is independent. An old importer mistakenly removed the text containing the less-than sign, and this site has restored it.

This site uses a standard input/output protocol.

输入格式

The first line contains T (1..10). Each test case consists of one line with N (2..100000), followed by one line with N integers (1..3000).

输出格式

For each test case, output one line with the product modulo 1000000007.

样例 1

输入：

1
4
1 2 3 7

输出：

720

样例 2

输入：

1
3
4 3 7

输出：

84

样例 3

输入：

2
2
2 2
2
1 2

输出：

0
3

样例说明

Example 1: the six factors 3, 2, 6, 1, 5, 4 multiply to 720. Example 2: the three factors 7, 3, 4 multiply to 84. Example 3: in the first test case, equal values XOR to 0, so output 0; in the second, the only factor is 3, so output 3.