Make the Partition

0

0 votes
Easy
Problem

Ayush normally loves solving arrays. However, when his friend gave him a problem on arrays, he found it difficult to solve and feels bad. Now it is your turn to help Ayush regain his interest by helping him. The problem is as follows :

Given an array of size N , find the number of ways to parition the array such that the product of numbers in each partition is negative.

Since the answer can be large output it modulo 1000000007.

INPUT FORMAT

The first line of input contains an integer N , denoting the size of the array.

The second line of input contains N integersdenoting  the elements of the array.

OUTPUT FORMAT

A single integer denoting the required answer.

CONSTRAINTS

1N105

104A[i]104

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?