XOR Sum

All submissions for this problem are available.
WARNING: This problem has large input / output files. Use of faster I/O methods is recommended.
Chef has a sequence of N positive integers { a_{1}, a_{2}, a_{3}, ... a_{N} }. The Sous Chef wants to choose another sequence of N nonnegative integers { b_{1}, b_{2}, b_{3}, ... b_{N} } such that
 The bitwise xor sum of these 2 sequences is equal
 i.e, a_{1} ^ a_{2} ^ a_{3} ^ ... a_{N} = b_{1} ^ b_{2} ^ b_{3} ^ ... b_{N}
 for each i, b_{i} ≤ a_{i}
The Sous Chef asks for your help. Your allegiance to the Chef withstanding, you tell him that you will not generate such a sequence for him. Instead, you will tell him the number of such sequences possible.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the length of your sequence. The second line contains N spaceseparated integers a_{1}, a_{2}, ..., a_{N}.
Output
For each test case, output a single line containing the number of ways your friend can choose his sequence. Since this number may be too big, output this number modulo 1000000009.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 100000
1 ≤ a_{i} ≤ 1000000000
Sample
Input 4 1 5 2 3 3 3 3 3 3 4 1 2 3 4 Output 1 4 16 6
Explanation
Test Case 1: The only possible sequence is { 5 }.
Test Case 2: There are 4 possible sequences whose bitwise xor is equal to 3^3 = 0
 { 0, 0 }
 { 1, 1 }
 { 2, 2 }
 { 3, 3 }
Test Case 4: The 6 possible sequences are
 { 0, 0, 0, 4 }
 { 0, 1, 1, 4 }
 { 1, 0, 1, 4 }
 { 1, 1, 0, 4 }
 { 0, 2, 2, 4 }
 { 1, 2, 3, 4 }
Author:  satej 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/AMXOR 
Tags  cook34, dynamicprogramming, medium, satej 
Date Added:  10052013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 