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 integers, denoting the elements of the array.
OUTPUT FORMAT
A single integer denoting the required answer.
CONSTRAINTS
1≤N≤105
−104≤A[i]≤104