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 $A$ and $B$ are valid expressions, then so are $min(A,B)$ and $max(A,B)$, 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 $min(min(?,?),min(?,?))$ and $max(max(?,?),min(?,?))$ are valid according to the definition above, but expressions $??$, $max(min(?))$ and $min(?,?,?)$ are not.

Helena is given a valid expression containing a total of $N$ question marks. Each question mark is to be replaced with a number from the set $\{1,2,\dots ,N\}$ 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 $1$ to $N$.

Once the question marks have been replaced by numbers, the expression can be evaluated and its value will be an integer between $1$ and $N$. 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 $1$ and $N$, the number of different values obtainable by evaluating the expression.

Constraints

For all subtasks:

$2\le N\le 1000000$

Subtask	Score	Constraints
$1$	$10$	$N\le 9$
$2$	$13$	$N\le 16$
$3$	$13$	Each function in the expression has at least one question mark as an argument.
$4$	$30$	$N\le 1000$
$5$	$34$	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 $\{1,2,3,4\}$, which is $1$. Therefore, there is only one possible value.

Sample Input 2

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

Sample Output 2

2

Explanation for Sample 2

The numbers $3$ and $4$ can be obtained as $4=max(4,max(3,min(2,1)))$ and $3=max(3,max(2,min(1,4)))$. It can be shown that values $1$ and $2$ are not attainable and so the answer is $2$.

Sample Input 3

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

Sample Output 3

3