Brackets#439

Brackets

1 second

64 megabytes

Easy

Given an expression consisting only of the letter $a$ and the operation signs $+$ and $*$ . Write a program that computes the number of ways to place a full set of parentheses in this expression so that each pair of parentheses contains one operation sign and two operands, each of which is either the letter $a$ or an expression in parentheses. The value of the expression must remain unchanged, that is, multiplication operations must be performed before addition operations. For example, for the expression $a + a + a * a * a$ a+a+a*a*a there are $4$ ways to place the parentheses:

$(a + (a + (a * (a * a))))$ (a+(a+(a*(a*a))))

$(a + (a + ((a * a) * a)))$ (a+(a+((a*a)*a)))

$((a + a) + ((a * a) * a))$ ((a+a)+((a*a)*a))

$((a + a) + (a * (a * a)))$ ((a+a)+(a*(a*a)))

Input

The first line contains a valid expression with no more than $25$ operation signs.

Output

Print the number of ways to place the parentheses.

Examples

Example 1

Loading

a + a + a * a * a

(a + (a + (a * (a * a))))

(a + (a + ((a * a) * a)))

((a + a) + ((a * a) * a))

((a + a) + (a * (a * a)))