# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* likhon5

*iceknight1093*

**Tester & Editorialist:**# DIFFICULTY:

1612

# PREREQUISITES:

Basic combinatorics

# PROBLEM:

You’re given an array A. Find the number of non-empty subsets of indices whose removal results in every subarray having even sum.

# EXPLANATION:

Suppose we removed some indices, and the array satisfies the given condition, i.e, \displaystyle\sum_{k=i}^j A_k is even, for each 1 \leq i \leq j \leq |A|.

Then, in particular this holds for i = j, which means every element must itself be even.

Of course, if every element is even then every subarray sum is also even; so we’ve reduced our problem to counting the number of ways of removing indices such that all remaining elements are even.

That’s not too hard:

- First,
*all*odd elements must be removed. - Suppose this leaves K even elements. We can then choose any subset of them to remove, for 2^K possible ways.

There’s one edge case: since the statement asks for **non-empty** subsets, if K = N (i.e all elements of the original array are even), the answer is 2^N - 1; since we can’t choose the empty subset.

Since K \leq N, computing 2^K can be done by just repeated multiplication using a loop.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Author's code (C++)

```
#include <bits/stdc++.h>
#define endl '\n'
#define filein freopen("input20.in","r",stdin)
#define fileout freopen("output20.out","w",stdout)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mx=2e5+9;
const int mod=1e9+7;
int main()
{
fast;
int t; cin>>t;
assert(t<=10000);
int total=0;
while(t--)
{
int n; cin>>n;
total+=n;
int odd=0,even=0;
for(int i=0;i<n;i++)
{
int x; cin>>x;
assert(x>=0 and x<=200000);
if(x%2) odd++;
else even++;
}
long long cnt=1;
for(int i=1;i<=even;i++) cnt=(cnt*2)%mod;
if(odd) cout<<cnt<<endl;
else cout<<cnt-1<<endl;
}
assert(total<=200000);
}
```

## Editorialist's code (Python)

```
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
evens = 0
for x in a: evens += (x+1)%2
ans = pow(2, evens, mod)
if evens == n: ans -= 1
print(ans%mod)
```