#P1463. 数组分割

数组分割

问题描述

小蓝有 NN 张卡片,每张卡片上都写着一个整数,分别是 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1}。

现在,小蓝准备把这些卡片分成两组,放进两个盒子里。

分组时需要满足:

  • 每张卡片都必须放进一个盒子,不能遗漏。
  • 每张卡片只能放进一个盒子。
  • 第一个盒子里所有数字的和必须是偶数。
  • 第二个盒子里所有数字的和也必须是偶数。

如果一个盒子里没有卡片,那么这些数字的和就看作 00,而 00 是偶数。

请问,小蓝有多少种不同的分组方法?

注意: 只要有一张卡片放入的盒子不同,就算作一种新的分组方法。

输入格式

第一行一个整数 TT,表示有 TT 组数据。

接下来输入 TT 组数据,每组数据包含两行:第一行一个整数 NN,表示数组 AA 的长度;第二行输入 NN 个整数从左至右依次为 A0,A1,...,AN−1A_0, A_1, ..., A_{N-1},相邻元素之间用空格分隔。

输出格式

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

样例输入

2
2
6 6
2
1 6

样例输出

4
0

说明

对于第一组数据,答案为 44。(注意:大括号内的数字表示元素在数组中的下标。)

  • R1={0},R2={1}R_1 = \{0\}, R_2 = \{1\};此时 S1=A0=6S_1 = A_0 = 6 为偶数,S2=A1=6S_2 = A_1 = 6 为偶数。
  • R1={1},R2={0}R_1 = \{1\}, R_2 = \{0\};此时 S1=A1=6S_1 = A_1 = 6 为偶数,S2=A0=6S_2 = A_0 = 6 为偶数。
  • R1={0,1},R2={}R_1 = \{0, 1\}, R_2 = \{\};此时 S1=A0+A1=12S_1 = A_0 + A_1 = 12 为偶数,S2=0S_2 = 0 为偶数。
  • R1={},R2={0,1}R_1 = \{\}, R_2 = \{0, 1\};此时 S1=0S_1 = 0 为偶数,S2=A0+A1=12S_2 = A_0 + A_1 = 12 为偶数。

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

评测数据与规模

  • 对于 20%20\% 的评测用例,1≤N≤101 \leq N \leq 10。
  • 对于 40%40\% 的评测用例,1≤N≤1021 \leq N \leq 10^2。
  • 对于 100%100\% 的评测用例,$1 \leq T \leq 10, 1 \leq N \leq 10^3, 0 \leq A_i \leq 10^9$。