Brackets

Subtraction is not associative. For example $(5-2)-1 = 2$, but $5-(2-1) = 4$, so $(5-2)-1 \neq 5-(2-1)$. This means the value of an expression such as $5-2-1$ depends on the order in which the subtractions are carried out. When no brackets are written, the operations are performed from left to right, so $5-2-1$ means $(5-2)-1$.

You are given an expression of the form

$x_1 \pm x_2 \pm \cdots \pm x_n,$

where each $\pm$ is either $+$ (plus) or $-$ (minus), and $x_1, x_2, \ldots, x_n$ are pairwise distinct variables.

Into the all-minus expression

$x_1 - x_2 - \cdots - x_n$

you want to insert brackets so that the result is equivalent to the given expression. For example, to obtain an expression equivalent to

$x_1 - x_2 - x_3 + x_4 + x_5 - x_6 + x_7,$

you may bracket $x_1 - x_2 - x_3 - x_4 - x_5 - x_6 - x_7$ as

$(((x_1 - x_2) - ((x_3 - x_4) - x_5)) - (x_6 - x_7)).$

We consider only fully and correctly bracketed expressions. An expression is fully and correctly bracketed when it is:

• a single variable, or
• of the form $(w_1 - w_2)$, where $w_1$ and $w_2$ are themselves fully and correctly bracketed expressions.

Expressions with redundant brackets, such as $()$, $(x_i)$, or $((\cdots))$, are not allowed. The expression $x_1 - (x_2 - x_3)$ is not fully bracketed either, because it lacks the outermost brackets.

Write a program that reads the given expression and computes, modulo $1{,}000{,}000{,}000$, the number of different ways to insert $n-1$ pairs of brackets into $x_1 - x_2 - \cdots - x_n$ so that the order of the subtractions is fully determined and the resulting expression is equivalent to the given one.

The first line contains one integer $n$ with $2 \le n \le 5000$, the number of variables. Each of the next $n-1$ lines contains a single character, $+$ or $-$. The character on the $i$-th of these lines is the operator between $x_i$ and $x_{i+1}$ in the given expression.

Print a single integer: the number of different ways, modulo $1{,}000{,}000{,}000$, to insert $n-1$ pairs of brackets into $x_1 - x_2 - \cdots - x_n$ so that the order of the subtractions is fully determined and the resulting expression is equivalent to the given one.