


Brackets
The operation of subtraction is not associative, e.g. (52)1=2, but 5(21)=4, therefore (52)1<>5(21). It implies that the value of the expression of the form 521 depends on the order of performing subtractions. Usually in lack of brackets we assume that the operations are performed from left to right, i.e. the expression 521 is equivalent to the expression (52)1. We are given an expression of the form x_{1} +/ x_{2} +/ ... +/ x_{n}, where each +/ denotes either + (plus) or  (minus), and x_{1},x_{2},...,x_{n} denote (pairwise) distinct variables. In an expression of the form x_{1}x_{2}...x_{n} we want to insert n1 pairs of brackets to unambiguously determine the order of performing subtractions and, in the same time, 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
Informally speaking, we are not interested in expressions containing spare brackets like: (), (x_{i}), ((...)). But the expression x_{1}(x_{2}x_{3}) is not fully bracketed because it lacks the outermost brackets. TaskWrite a program which:
InputIn the first line of the text file naw.in there is one integer n, 2<=n<=5000. This is the number of variables in the given expression. In each of the following n1 lines there is one character: + or . In the ith line there is the sign appearing between x_{i1} and x_{i} in the given expression.OutputIn the first line of the text file naw.out your program should write one integer equal to the number of different ways (modulus 1 000 000 000) in which n1 pairs of brackets may be inserted into the expression x_{1}x_{2}...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.ExampleFor the following input file naw.in:7   + +  +the correct answer is in the following output file naw.out: 3 Print friendly version 