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, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## 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