|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||8||4||2||40.000%|
The operation of subtraction is not associative, e.g. (5-2)-1=2, but 5-(2-1)=4, therefore (5-2)-1≠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
where each ± denotes either + (plus) or - (minus), and x1,x2,…,xn denote (pairwise) distinct variables. In an expression of the form
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
we may insert brackets into
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: (), (xi), ((…)). But the expression x1-(x2-x3) is not fully bracketed because it lacks the outermost brackets.
Write a program which:
In the first line of the standard input there is one integer n, 2 ≤ n ≤ 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 xi-1 and xi in the given expression.
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 x1-x2-…-xn so as to unambiguously determine the order of performing subtractions and, in the same time, to obtain an expression equivalent to the given one.
7 - - + + - +