eolymp
bolt
Try our new interface for solving problems
Problems

Brackets

Brackets

Time limit 1 second
Memory limit 64 MiB

Given an expression consisting only of letters a digits and the operations + and *. Write a program that computes the number of ways of placing a full set of brackets in this expression so that each pair of brackets contain a single character operation and two operands, each of which is either a letter or an expression in parentheses. Value of the expression at the same time should remain unchanged, ie must first run the operations of multiplication and then addition. For example, the expression а+а+а*а*а there are 4 ways to placement of brackets:

(а+(а+(а*(а*а))))

(а+(а+((а*а)*а)))

((а+а)+((а*а)*а))

((а+а)+(а*(а*а)))

Input data

In the first line of the input file contains a valid expression containing no more than 25 characters of operations.

Output data

In the output file display one number - the number of ways of placing parentheses.

Examples

Input example #1
a+a+a*a*a
Output example #1
4