XOR-Split!
Tag(s):

Dynamic Programming, Gaussian Elimination, Medium

Problem
Editorial
Analytics

Doing even the easiest of tasks in the most complicated way, is what ThunderCracker is expert at! Recently, he came across a simple problem :

"Given an array $A$ of positive integers, find if it is possible to divide it into 2 subsets, such that every element in $A$ belongs to exactly one subset, and both the subsets thus formed are exactly the same."

(Two subsets are said to be same if they contain the same elements and the frequency of all elements is the same in both of them)

For example, $[1, 1, 2, 2]$ can be divided into $[1, 2]$ and $[1, 2]$.
$[1, 2, 3, 1]$ , however, has no such division.

To solve this problem, ThunderCracker came up with a super-weird solution. He found the $XOR$ of all elements in the array! He believes that a division is possible if the $XOR$ is $0$. Otherwise, it is not.

Soon, he realised that the solution doesn't work for every array. ($[1, 2, 3]$, for example!)

Nonetheless, he came up with an interesting task for you :

" Given an array $A$, find the number of non-empty subsequences of $A$, where ThunderCracker's solution gives the correct output! "

Input format

The first line of the input consists of a single integer $T$, denoting the number of test cases. $T$ test cases follow.

The first line of a test case contains a single integer $N$, denoting the size of array $A$.

The second line contains $N$ space separated integers, that represent the array $A$.

Output format

For every test case, print on a new line, a single integer, that is the number of subsequences of $A$, where ThunderCracker's solution matches the expected output. As the answer can be very large, output it modulo $1000000007$. ($10^9 + 7$)

Constraints

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^5$
$1 ≤ A[i] ≤ 10^9$

$1 \leq A[i] \leq 20$ $20\%$
$1 \leq A[i] \leq 1000$ $50\%$
Original Constraints $30\%$
SAMPLE INPUT
2
3
1 2 3
4
1 2 1 2
SAMPLE OUTPUT
6
15
Explanation

For the first test case, let us check for all the non-empty subsequences of A.

{1} No No
{2} No No
{3} No No
{1, 2} No No
{1, 3} No No
{2, 3} No No
{1, 2, 3} No Yes
Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...