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

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
n = int(input())
a = input().split()
len_arr = len(a)
arr = []
dp = []
mod = 1000000007
for i in range(len_arr):
	arr.append(int(a[i]))
for i in range(len_arr):
	dp.append([0] * len_arr)
for i in range(len_arr):
	for j in range(len_arr):
		if i == j:
			continue
		if i == 0 or j > i:
			continue
		dp[j][i] = dp[j][i - 1]
		if arr[i] > 0:
			for k in range(j, i, 1):
				if arr[k] < 0 and arr[i] == -arr[k] and (k != j):
					dp[j][i] = ((dp[j][i] + 1 + dp[k + 1][i - 1]) % mod + (1 + dp[k + 1][i - 1]) % mod * dp[j][k - 1] % mod) % mod
				elif arr[k] < 0 and arr[i] == -arr[k] and (k == j):
					dp[j][i] = (dp[j][i] + 1 % mod + dp[k + 1][i - 1]) % mod
print(dp[0][n - 1] + 1)


import sys
input()
raw = [i for i in map(int, input().split())]

def balanced(l):
	open = []
	for i in l:
		if i < 0:
			open.append(-1 * i)
		if i > 0:
			if open.pop() != i:
				return 0
	if open == []:
		return 1
	return 0

def even(l):
	while l != []:
		if not l[0] * -1 in l:
			return 0
		l.remove(l[0] * -1)
		l.pop(0)
	return 1

def removeodds(l):
	toreturn = []
	for i in l:
		if i < 0 and -1 * i in l[l.index(i):]:
			toreturn.append(i)
		if i > 0 and -1 * i in l[:l.index(i)]:
			toreturn.append(i)
	return toreturn

def getvalue(l):
	if l == []:
		return 1
	closepos = l.index(-1 * l[0])
	if even(l[1:closepos]):
		return 2 * getvalue(l[1:closepos]) * getvalue(l[closepos + 1:])
	else:
		topass1 = l[:]
		topass1.pop(closepos)
		topass1.pop(0)
		topass2 = removeodds(l[1:closepos]) + removeodds(l[closepos + 1:])
		return getvalue(topass1) + getvalue(topass2)
l = removeodds(raw)
print(getvalue(l) % (10 ** 9 + 7))


MOD = 1000000007
n = int(input())
s = [int(x) for x in input().split()]
vi = {}
for (i, x) in enumerate(s):
	if x not in vi:
		vi[x] = []
	vi[x].append(i)
c = {}

def search(b, e):
	if (b, e) in c:
		return c[b, e]
	val = 1
	for i in range(b, e):
		if s[i] < 0 and -s[i] in vi:
			for ni in vi[-s[i]]:
				if ni >= b and ni <= e:
					val = (val + search(i + 1, ni - 1) * search(ni + 1, e)) % MOD
	c[b, e] = val
	return val
print(search(0, n - 1))