The operation of subtraction is not associative, e.g. $(5-2)-1=2$, but $5-(2-1)=4$, therefore $(5-2)-1 \ne 5-(2-1)$. It implies that the value of the expression of the form $5-2-1$ depends on the order of performing subtractions. In lack of brackets we assume that the operations are performed from left to right, i.e. the expression $5-2-1$ denotes $(5-2)-1$. We are given an expression of the form

$$x_1 \pm x_2 \pm \ldots \pm x_n$$

where each $\pm$ denotes either $+$ (plus) or $-$ (minus), and $x_1,x_2,\ldots ,x_n$ denote (pairwise) distinct variables. In an expression of the form

$$x_1-x_2- \ldots - x_n$$

we want to insert brackets in such a way as to obtain an expression equivalent to the given one. For example, if we want to obtain an expression equivalent to the expression

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

we may insert brackets into

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

as follows:

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

Note: We are interested only in fully and correctly bracketed expressions. An expression is fully and correctly bracketed when it is

• either a single variable,
• or an expression of the form $(w_1-w_2)$, in which $w_1$ and $w_2$ are fully and correctly bracketed expressions.

Informally speaking, we are not interested in expressions containing spare brackets like: $()$, $(x_i)$, $((\ldots ))$. But the expression $x_1-(x_2-x_3)$ is not fully bracketed because it lacks the outermost brackets.

Task

Write a program which:

• reads from the standard input the description of the given expression of the form $x_1 \pm x_2 \pm \ldots \pm x_n$,
• computes the number of different ways (modulus $1\,000\,000\,000$) in which n-1 pairs of brackets may be inserted into the expression $x_1-x_2-\ldots -x_n$ so as to unambiguously determine the order of performing subtractions and, in the same time, to obtain an expression equivalent to the given one,
• writes the result to the standard output.

Input

In the first line of the standard input there is one integer $n$, $2 \le n \le 5\,000$. This is the number of variables in the given expression. In each of the following $n-1$ lines there is one character $+$ or $-$. In the $i$-th line there is the sign appearing between $x_{i-1}$ and $x_i$ in the given expression.

Output

In the first line of the standard output your program should write one integer equal to the number of different ways (modulus $1\,000\,000\,000$) in which $n-1$ pairs of brackets may be inserted into the expression $x_1-x_2- \ldots - x_n$ so as to unambiguously determine the order of performing subtractions and, in the same time, to obtain an expression equivalent to the given one.

Example

Input

7
-
-
+
+
-
+

Output

3