问题描述

小蓝有一个长度为 $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∈R_1}A_r$，$S_2=\sum_{r∈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≤N≤10$。

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

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