[naglowek]
IX OI 2001/2002
 
Railways
Byteasar the Travelling Salesman
Superknight
Island
Castle
Insulator
Parcel
Counting-Out Rhyme
Ski Resort
Protocols
Minuses
Skiers
Balance
B-Smooth Numbers
Brackets
Cipher
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994

Main page

Polish version
 
IX Olimpiada Informatyczna 2001/2002

Task: naw
Author: Piotr Chrz?stowski-Wachtel, Wojciech Guzicki
Brackets

III stage contest  

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

x1 +/- x2 +/- ... +/- xn,

where each +/- denotes either + (plus) or - (minus), and x1,x2,...,xn denote (pairwise) distinct variables. In an expression of the form

x1-x2-...-xn

we want to insert n-1 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

x1-x2-x3+x4+x5-x6+x7

we may insert brackets into

x1-x2-x3-x4-x5-x6-x7

as follows:

(((x1-x2)-((x3-x4)-x5))-(x6-x7)).

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 (w1-w2), in which w1 and w2 are fully and correctly bracketed expressions.

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.

Task

Write a program which:
  • reads from the text file naw.in the description of the given expression of the form x1 +/- x2 +/- ... +/- xn,
  • computes 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,
  • writes the result to the text file naw.out.

Input

In 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 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.

Output

In 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 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.

Example

For the following input file naw.in:
7
-
-
+
+
-
+
the correct answer is in the following output file naw.out:
3