You are given an array (a_1, a_2, \ldots, a_n). Also, you are given three variables (P,Q,R), initially equal to zero. You need to process all the numbers (a_1, a_2, \ldots, a_n), in the order from (1) to (n) . When processing the next (a_i), you must perform exactly one of the three actions of your choice: (P := P \oplus a_i) (Q := Q \oplus a_i) (R := R \oplus a_i) (\oplus) denotes the bitwise XOR operation . When performing actions, you must follow the main rule : it is necessary that after each action, all three numbers (P,Q,R) are not pairwise distinct. There are a total of (3^n) ways to perform all (n) actions. How many of them do not violate the main rule ? Since the answer can be quite large, find it modulo (10^9 + 7). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains an integer (n) ((1 \le n \le 2 \cdot 10^5)) — the length of the array (a). The second line of each test case contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \le a_i \le 10^9)) — the elements of the array (a). It is guaranteed that the sum of the values of (n) for all test cases does not exceed (2 \cdot 10^5). For each test case, output the number of ways to perform all (n) actions without violating the main rule , modulo (10^9 + 7). In the first test case, there are 3 valid sequences of operations: PPP , QQQ , RRR . In the second test case, there are 9 valid sequences of operations: PPPP , PPPQ , PPPR , QQQP , QQQQ , QQQR , RRRP , RRRQ , RRRR .