Ankit, Srijan and a game of stone piles

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
There are N piles of stones, where ith pile has A_{i} stones. A game is played on these piles, in order from pile 1 to N. When the game is on the ith pile, a player can remove any nonzero number of stones from this pile in a single move. If the current pile becomes empty, the game moves on to the next pile. The player who is unable to make a move loses.
Srijan and Ankit are going to play this game. Ankit, being younger, always gets to start the game. However, Srijan, being clever, sneaks into the game arena early and permutes the order of piles. Then, the game is played on this new order of piles. Your task is to find out the number of orders in which the piles can be arranged so that Ankit wins the game. Assume that both the players play optimally. Since the answer can be very large, output it modulo 10^{9} + 7.
Note that two orders are considered different if their contents are different. Formally, two orders A and B are different if there exists an index k (1 ≤ k ≤ N) such that A_{k} != B_{k}.
Input
 The first line contains an integer T, denoting the number of test cases to follow. Each of the test cases contains exactly two lines.
 The first line for each test case contains an integer N, denoting the number of piles, and the next line contains N spaceseparated integers, denoting the number of stones in the piles.
Output
For each test case, output a single integer corresponding to the answer for that test case.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{10}
 The sum of values of N over all test cases does not exceed 10^{6}.
Example:
Sample input:
2 3 1 1 2 2 2 3
Sample Output:
2 2
Explanation:
Case 1:
The following different orders are possible:
[1, 1, 2]
Ankit removes the only stone in the first pile.
Srijan removes the only stone in the second pile.
Ankit removes both the stones in the second pile.
Ankit wins.
[1, 2, 1]
Ankit removes the only stone in the first pile.
Srijan takes one stone from then the second pile. Ankit removes the remaining one stone from the second pile.
Srijan removes the only stone in the third pile.
Srijan wins.
[2, 1, 1]
Ankit removes both the stones in the first pile.
Srijan removes the only stone in the second pile.
Ankit removes the only stone in the second pile.
Ankit wins.
Thus, Ankit wins on 2 different orders.
Author:  code_master01 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/ANKGAME 
Tags  code_master01, combinatorics, cook59, counting, easymedium, gametheory 
Date Added:  31032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions