Solve the programming task below in a Python markdown code block.
Read problems statements in Mandarin Chinese  and Russian. 

Chef loves brackets. So much so, that rather than just use plain brackets like (), {}, or [], he has invented his own notation that allows him to use many more types of brackets.

Each type of bracket is designated by an integer. A negative integer -x represents an opening bracket of type x; while a positive integer x represents a closing bracket of type x. Any sequence of such integers is then called a bracket-pair sequence.

A balanced bracket-pair sequence can be defined recursively as follows:

	The empty sequence is a balanced bracket-pair sequence.
	If S is a balanced bracket-pair sequence, then -x S x is a balanced bracket-pair sequence for any positive integer x.
	If S and T are balanced bracket-pair sequences, then S T is a balanced bracket-pair sequence.

For example, "-1 -2 2 -3 -4 4 3 1" is a balanced bracket-pair sequence, but "-1 -2 1 2" is not.

Chef has a bracket-pair sequence (which may or may not be balanced) consisting of N integers. There are 2^{}N ways to form a subsequence of his sequence. He wants to know how many of these subsequences are balanced.

Help him to calculate this number, modulo 10^{9}+7. 

------ Input ------ 

The first line contains a single integer N denoting the number of brackets in his sequence. 
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the types of brackets. A negative number means an opening bracket; a positive number means a closing bracket.

------ Output ------ 

In a single line print the required answer.

------ Constraints ------ 

$1 ≤ N ≤ 100$
$-10^{9} ≤ A_{i} ≤ 10^{9}$$A_{i} ≠  0$
$It is not guaranteed that each opening bracket has a closing bracket of same type and vice-versa. $

------ Subtasks ------ 

$Subtask N ≤ 10 Points: 10 $
$Subtask N ≤ 20 Points: 15 $
$Subtask N ≤ 100 Points: 75 $

------ Example ------ 

Input:
11
-1 -2 9 2 -3 -4 3 4 8 8 1 

Output:
12