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

x₁ +/- x₂ +/- ... +/- x_n,

where each +/- denotes either + (plus) or - (minus), and x₁,x₂,...,x_n denote (pairwise) distinct variables. In an expression of the form

x₁-x₂-...-x_n

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

x₁-x₂-x₃+x₄+x₅-x₆+x₇

we may insert brackets into

x₁-x₂-x₃-x₄-x₅-x₆-x₇

as follows:

(((x₁-x₂)-((x₃-x₄)-x₅))-(x₆-x₇)).

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

Informally speaking, we are not interested in expressions containing spare brackets like: (), (x_i), ((...)). But the expression x₁-(x₂-x₃) is not fully bracketed because it lacks the outermost brackets.

Task

• reads from the text file naw.in the description of the given expression of the form x₁ +/- x₂ +/- ... +/- 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₁-x₂-...-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.

Input

Output

Example

7
-
-
+
+
-
+

3

Print friendly version