Even Sum
Tag(s):

## Easy-Medium, Implementation, Math

Problem
Editorial
Analytics

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$

SAMPLE INPUT
3
2 2 2
SAMPLE OUTPUT
5
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] ]

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Greedy Technique)

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Greedy Algorithms
• Algorithms > Greedy Algorithms
• Algorithms > Greedy Algorithms