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 1\,000\,000~

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 1\,000~
~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