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 :
1≤N≤2∗1051≤a[i]≤1015
Note: Use 64-bit integer data type
So all possible subsequences are
(2),(4),(2,4),(2,1,3),(4,1,3),(2,4,1,3),(1,3)