시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB444100.000%

문제

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 math 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?

입력

The first and only line contains a single valid expression.

출력

Output a single integer between $1$ and $N$, the number of different values obtainable by evaluating the expression.

제한

In all subtasks it holds that $2 ≤ N ≤ 1\,000\,000$.

서브태스크

번호배점제한
110

$N ≤ 9$

213

$N ≤ 16$

313

Each function in the expression has at least one question mark as an argument.

430

$N ≤ 1000$

534

No additional constraints.

예제 입력 1

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

예제 출력 1

1

No matter how the numbers are assigned, the value of the resulting expression will always equal to the minimum of the set $\{1, 2, 3, 4\}$, which is $1$. Therefore, there is only one possible value.

예제 입력 2

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

예제 출력 2

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$.

예제 입력 3

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

예제 출력 3

3

채점 및 기타 정보

  • 예제는 채점하지 않는다.