Problem Description

This is a problem from Helena’s math homework.

We define valid expressions as follows:

• ? is a valid expression, representing an unknown.
• If $A, B$ are both valid expressions, then min($A$,$B$) and max($A$,$B$) are both valid expressions, representing taking the minimum / maximum of the left and right sides, respectively.

Let the number of ? be $N$. Now a valid expression is given. If we replace each question mark with any number from $1$ to $N$, and each number can be used at most once, how many different final results can be obtained?

Poor Helena cannot solve it. Please help her.

Input Format

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

Output Format

Output one integer, representing the number of distinct results.

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

1

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

2

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

3

Hint

Sample 1 Explanation

No matter how the values are chosen, the final result will be $\min\{1,2,3,4\}$, i.e. $1$.

Sample 2 Explanation

One assignment that yields the answer $4$ is: 4=max(4,max(3,min(2,1))).
One assignment that yields the answer $3$ is: 3=max(3,max(2,min(1,4))).
It can be proven that the answer cannot be $1$ or $2$.

Constraints

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

Translated by ChatGPT 5