Brackets
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. Usually in lack of brackets we assume that the operations are performed from left to right, i.e. the expression 5-2-1 is equivalent to the expression (5-2)-1. We are given an expression of the form
where each +/- denotes either + (plus) or - (minus), and
we want to insert
we may insert brackets into
as follows: (((
- 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_{1}-(x_{2}-x_{3}) is
not fully bracketed because it lacks the outermost brackets.## TaskWrite a program which:- reads from the text file
`naw.in`the description of the given expression of the form*x*_{1}+/-*x*_{2}+/- ... +/-*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}-...-*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 text file
`naw.out`.
## InputIn the first line of the text filenaw.in there is one
integer n, 2<=n<=5000. 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.
## OutputIn the first line of the text filenaw.out 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}-...-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 filenaw.in:
7 - - + + - +the correct answer is in the following output file naw.out:
3 |