### 问题描述

小蓝有一个长度为 $N$ 的数组 $A = [A_0 ,A_1 ,...,A_{N-1}]$。现在小蓝想要从 $A$ 对应的数组下标所构成的集合 $I = {0,1,2,...,N - 1}$ 中找出一个子集 $R_1$ ，那么 $R_1$ 在 $I$ 中的补集为 $R_2$ 。记 $S_1 = \sum_{r \in R_1} A_r$ ，$S_2 = \sum_{r \in R_2} A_r$ ，我们要求 $S_1$ 和 $S_2$ 均为偶数，请问在这种情况下共有多少种不同的 $R_1$ 。当 $R_1$ 或 $R_2$ 为空集时我们将 $S_1$ 或 $S_2$ 视为 $0$。

输入格式

第一行一个整数 $T$，表示有 $T$ 组数据。

接下来输入 $T$ 组数据，每组数据包含两行：第一行一个整数 $N$，表示数组 $A$ 的长度；第二行输入 $N$ 个整数从左至右依次为 $A_0 ,A_1 ,...,A_{N-1}$ ，相邻元素之间用空格分隔。

输出格式

对于每组数据，输出一行，包含一个整数表示答案，答案可能会很大，你需要将答案对 $1000000007$ 进行取模后输出。

样例输入

2
2
6 6
2
1 6

样例输出

4
0

样例说明

对于第一组数据，答案为 $4$。（注意：大括号内的数字表示元素在数组中的下标。）

$R_1 = {0},R_2 = {1}$ ；此时 $S_1 = A_0 = 6$ 为偶数, $S_2 = A_1 = 6$ 为偶数。

$R_1 = {1},R_2 = {0}$ ；此时 $S_1 = A_1 = 6$ 为偶数, $S_2 = A_0 = 6$ 为偶数。

$R_1 = {0,1},R_2 = {}$ ；此时 $S_1 = A_0 + A_1 = 12$ 为偶数, $S_2 = 0$ 为偶数。

$R_1 = {},R_2 = {0,1}$ ；此时 $S_1 = 0$ 为偶数, $S_2 = A_0 + A_1 = 12$ 为偶数。

对于第二组数据，无论怎么选择，都不满足条件，所以答案为 $0$。

评测用例规模与约定

对于 $$20$$ % 的评测用例，$1 \leq N \leq 10$。

对于 $$40$$ % 的评测用例，$1 \leq N \leq 10^2$ 。

对于 $100$% 的评测用例，$1 \leq T \leq 10, 1 \leq N \leq 10^3 , 0 \leq A_i \leq 10^9$