Sum is Even
Problem
You are given an array of N integers. Now, you need to select two non-overlapping subarrays from this array such that the sum of each subarray selected is divisible by 2.
You need to output the number of ways in which you can select such two such subarrays.
As the answer can be rather large, print it Modulo 109+7
Note: Two subarrays are said to be non-overlapping if they have no element in common.
Input:
First line will contain the number of integers denoted by N The second line contains N space separated integers, where the ith integer denotes A[i].
Output: :
Print the required answer on a single line.
Constraints:
1≤N≤105 0≤|A[i]|≤109
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
The following selections are valid for the sample case : 1) [ A[0] ], [ A[1] ] 2) [ A[0] ] , [ A[2] ] 3) [ A[0] ] , [ A[1] + A[2] ] 4) [ A[1] ] , [ A[2] ] 5) [ A[0] + A[1] ] , [ A[2] ]
