题目描述

小蓝有一个长度为 $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 = \displaystyle \sum_{r \in R_1} A_r$，$S_2 = \displaystyle \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}$，相邻元素之间用空格分隔。

输出格式

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

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$。