Little Helena recently finished her first year of primary school. She is a model student, has straight A's, and has a huge passion for mathematics. She is currently on a well-deserved vacation with her family, but she's starting to miss her daily homework. Luckily, her older brother decided to quench her intellectual thirst, and gave her the following problem.
A valid expression is defined recursively as follows:
- the string
?
is a valid expression which represents a number. - if and are valid expressions, then so are and , where the former represents a function returning the smaller of its two arguments, while the latter represents a function returning the larger of its two arguments.
For example, expressions and are valid according to the definition above, but expressions , and are not.
Helena is given a valid expression containing a total of question marks. Each question mark is to be replaced with a number from the set in such a way that each number from this set appears exactly once in the expression. In other words, the question marks are replaced by a permutation of the numbers from to .
Once the question marks have been replaced by numbers, the expression can be evaluated and its value will be an integer between and . Considering all the ways of assigning numbers to question marks, how many different values can Helena obtain after evaluating the expression?
Input Specification
The first and only line contains a single valid expression.
Output Specification
Output a single integer between and , the number of different values obtainable by evaluating the expression.
Constraints
For all subtasks:
Subtask | Score | Constraints |
---|---|---|
Each function in the expression has at least one question mark as an argument. | ||
No additional constraints. |
Sample Input 1
min(min(?,?),min(?,?))
Sample Output 1
1
Explanation for Sample 1
No matter how the numbers are assigned, the value of the resulting expression will always be equal to the minimum of the set , which is . Therefore, there is only one possible value.
Sample Input 2
max(?,max(?,min(?,?)))
Sample Output 2
2
Explanation for Sample 2
The numbers and can be obtained as and . It can be shown that values and are not attainable and so the answer is .
Sample Input 3
min(max(?,?),min(?,max(?,?)))
Sample Output 3
3
Comments