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

见题面

见题面