Chef and BracketPairs

All submissions for this problem are available.
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 bracketpair sequence.
A balanced bracketpair sequence can be defined recursively as follows:
 The empty sequence is a balanced bracketpair sequence.
 If S is a balanced bracketpair sequence, then x S x is a balanced bracketpair sequence for any positive integer x.
 If S and T are balanced bracketpair sequences, then S T is a balanced bracketpair sequence.
For example, "1 2 2 3 4 4 3 1" is a balanced bracketpair sequence, but "1 2 1 2" is not.
Chef has a bracketpair 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 spaceseparated 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 viceversa.
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
Author:  berezin 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/CHEFBR 
Tags  berezin, dec14, dynamicprogramming, easy 
Date Added:  20032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 