问题描述
小蓝有 N 张卡片,每张卡片上都写着一个整数,分别是 A0,A1,…,AN−1。
现在,小蓝准备把这些卡片分成两组,放进两个盒子里。
分组时需要满足:
- 每张卡片都必须放进一个盒子,不能遗漏。
- 每张卡片只能放进一个盒子。
- 第一个盒子里所有数字的和必须是偶数。
- 第二个盒子里所有数字的和也必须是偶数。
如果一个盒子里没有卡片,那么这些数字的和就看作 0,而 0 是偶数。
请问,小蓝有多少种不同的分组方法?
注意: 只要有一张卡片放入的盒子不同,就算作一种新的分组方法。
输入格式
第一行一个整数 T,表示有 T 组数据。
接下来输入 T 组数据,每组数据包含两行:第一行一个整数 N,表示数组 A 的长度;第二行输入 N 个整数从左至右依次为 A0,A1,...,AN−1,相邻元素之间用空格分隔。
输出格式
对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你需要将答案对 1000000007 进行取模后输出。
样例输入
2
2
6 6
2
1 6
样例输出
4
0
说明
对于第一组数据,答案为 4。(注意:大括号内的数字表示元素在数组中的下标。)
- R1={0},R2={1};此时 S1=A0=6 为偶数,S2=A1=6 为偶数。
- R1={1},R2={0};此时 S1=A1=6 为偶数,S2=A0=6 为偶数。
- R1={0,1},R2={};此时 S1=A0+A1=12 为偶数,S2=0 为偶数。
- R1={},R2={0,1};此时 S1=0 为偶数,S2=A0+A1=12 为偶数。
对于第二组数据,无论怎么选择,都不满足条件,所以答案为 0。
评测数据与规模
- 对于 20% 的评测用例,1≤N≤10。
- 对于 40% 的评测用例,1≤N≤102。
- 对于 100% 的评测用例,$1 \leq T \leq 10, 1 \leq N \leq 10^3, 0 \leq A_i \leq 10^9$。