Jeetesh normally loves solving arrays . However, when his friend Asnani gave him a problem on arrays, he found it difficult to solve and feels bad .Now it is your turn to help Jeetesh 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 :

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

The second line of input contains N integers ,denoting  the elements of the array.

OUTPUT :

A single integer denoting the required answer.

CONSTRAINTS :

\(1 \leq N \leq 10^5\)

\(-10^4 \leq array \ element \leq 10^4\)