In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

The operation of subtraction is not associative, e.g. , but , therefore . It implies that the value of the expression of the form 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 is equivalent to the expression .

We are given an expression of the form

where each denotes either (plus) or (minus), and denote (pairwise) distinct variables. In an expression of the form

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

we may insert brackets into

as follows:

**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 , in which and are fully and correctly bracketed expressions.

Informally speaking, we are not interested in expressions containing spare brackets like: , , . But the expression is not fully bracketed because it lacks the outermost brackets.

Write a program which:

- reads from the standard input in the description of the given expression of the form ,
- computes the number of different ways (modulus ) in which pairs of brackets may be inserted into the expression 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.

In the first line of the standard input there is one integer , . This is the number of variables in the given expression. In each of the following lines there is one character: or . In the -th line there is the sign appearing between and 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 ) in which pairs of brackets may be inserted into the expression so as to unambiguously determine the order of performing subtractions and, in the same time, to obtain an expression equivalent to the given one.

For the input data:

7 - - + + - +

the correct result is:

3

*Task authors: Piotr Chrzastowski-Wachtel, Wojciech Guzicki.*