Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today’s topic is Set Theory. For today’s game, she had given a set *A = {a _{1}, a_{2}, …a_{N}}* of

*N*integers to her students and asked them to play the game as follows.

At each step of the game she calls a random student and asks him/her to select a non-empty subset from set *A* such that this subset had not been selected earlier and the sum of subset should be even. This game ends when all possible subsets had been selected. Manasa needs your help in counting the total number of times students can be called assuming each student gives the right answer. **While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets**.

**Input Format**

The first line contains an integer *N* i.e. size of set *A*.

Next line will contain *N* integers, each representing an element of *A*.

**Output Format**

Print number of time students are called. As this number can be very large you have to print the answer *modulo (10 ^{9} + 7)*.

**Constraints**

1 ≤ *N* ≤ 10^{5}

0 ≤ *a _{i}* ≤ 10

^{4}, where

*i ∈ [1 .. N]*

**Problem link:** A Chocolate Fiesta

**Sample Input 00**

```
4
2 4 6 1
```

**Sample Output 00**

```
7
```

**Sample Input 01**

```
3
1 2 2
```

**Sample Output 01**

```
3
```

**Explanation**

There are 7 different ways in which a non-empty subset, with even sum, can be selected, i.e., *{2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}*.

For second sample test case, there are 3 different ways in which a non-empty subset, with even sum, can be selected, i.e., *{a _{2}}, {a_{3}}, {a_{2}, a_{3}}* which is equivalent to

*{2}, {2}, {2,2}*.

## Solution

**Even sum from even numbers**

We know that number of non empty subsets from a set of k numbers is

ans_even = 2^{k} - 1

So number of subsets such that sum of elements is even is 2^{k} - 1

where k = number of even numbers.

**Even sum from odd numbers**

The possible ways of choosing odd number such that sum is even is by choosing even number of odd numbers . Number of possible ways using combinatorics:

^{n}{C}_2 + ^{n}{C}_4 + … + ^{n}{C}_n

Here n = number of odd numbers,

The possible number of subsets will be

ans_odd = 2^{k-1} - 1

where k = number of odd numbers

**Total number of subsets such that sum is even:**

ans = ans_odd + ans_even + (ans_odd*ans_even)

**Note:** The reason for including * (ans_odd*ans_even)* is that, we could get a even sum if we select a set of even number of odd number and set of even numbers.

```
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define mod 1000000007
using namespace std;
int temp;
int main(){
unsigned long long ansev,ansod,ans;
long int n,noe,noo,i;
ansev = 1;
ansod = 1;
ans = 0
noe = noo = 0;
scanf("%ld",&n);
for(i=0;i<n;i++){
scanf("%d",&temp);
if(temp&1)
noo++;
else
noe++;
}
for(i=1;i<=noe;i++){
ansev = (long long)fmodl((ansev*2),mod);
}
ansev = ansev-1;
for(i=1;i<noo;i++){
ansod = (long long)fmodl((ansod*2),mod);
}
ansod = ansod-1;
ans = (long long)fmodl((ansod*ansev),mod);
ans = (long long)fmodl((ans+ansod),mod);
ans = (long long)fmodl((ans+ansev),mod);
printf("%llu\n",ans);
return 0;
}
```