Problem Description

This is a math problem from Helena's homework:

We define a valid expression as follows:

• ? is a valid expression, representing an unknown number.
• If $A$ and $B$ are both valid expressions, then min($A$,$B$) and max($A$,$B$) are also valid expressions, representing the minimum and maximum values of the two sides, respectively.

Given that the number of ? is $N$, and a valid expression is provided, how many different results can be obtained by replacing each ? with any number from $1$ to $N$, ensuring that each number is used only once?

Poor Helena doesn't know how to solve it. Please help her.

Input Format

A single line containing a string representing the given valid expression.

Output Format

Output a single integer representing the number of different possible answers.

Sample Input and Output

Sample Input #1

min(min(?,?),min(?,?))

Sample Output #1

1

Sample Input #2

max(?,max(?,min(?,?)))

Sample Output #2

2

Sample Input #3

min(max(?,?),min(?,max(?,?)))

Sample Output #3

3

Notes

Explanation of Sample 1

Regardless of how the values are chosen, the final answer will always be $\min\{1,2,3,4\}$, which is $1$.

Explanation of Sample 2

The solutions yielding $4$ are: 4=max(4,max(3,min(2,1))), and the solutions yielding $3$ are: 3=max(3,max(2,min(1,4))). It can be proven that the answer cannot be $1$ or $2$.

Data Size and Constraints

For all data, $2 \le N \le 10^6$.

见题面 Input 部分

见题面 Output 部分