SOLVE
LATER
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 \(10^9+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 \(i^{th}\) integer denotes \(A[i]\).
Output: :
Print the required answer on a single line.
Constraints:
\( 1 \le N \le 10^5 \)
\( 0 \le | A[i] | \le 10^9 \)
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] ]