Good Sum

0

0 votes
C++, Counting, Math, Special Numbers, Combinatorics
Problem

Bob has an array A of length N and he wants to gift Alice a subsequence of this array
But Alice doesn't like a subsequence if the sum of the elements in that subsequence is odd
Find out how many subsequences can Bob gift her modulo 109+7

Input Format :
The first line contains N, the size of the array 
The second line contains N elements, representing the array A 

Output Format :
Print one integer, the number of possible ways Bob can gift Alice modulo 109+7

Constraints :

1N21051a[i]1015 

Note: Use 64-bit integer data type

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

So all possible subsequences are
(2),(4),(2,4),(2,1,3),(4,1,3),(2,4,1,3),(1,3)

Editor Image

?