### 问题描述 小蓝有一个长度为 $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$ 进行取模后输出。 ### 样例输入 ```text 2 2 6 6 2 1 6 ``` ### 样例输出 ```text 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$