P8997 [CEOI 2022] Homework

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.

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

Output one integer, representing the number of distinct results.

### 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$. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $N\le 9$ | $10$ | | $2$ | $N\le 16$ | $13$ | | $3$ | For any `min(`$A$`,`$B$`)` and `max(`$A$`,`$B$`)`, one of $A$ and $B$ is `?`. | $13$ | | $4$ | $N\le 10^3$ | $30$ | | $5$ | No special constraints. | $34$ | Translated by ChatGPT 5