P8997 [CEOI 2022] Homework

这是 Helena 的数学作业中的一道题： 我们定义合法表达式如下： - `?` 是合法表达式，这表示一个未知数。 - 如果 $A,B$ 均为合法表达式，那么 $\texttt{min(}A\texttt{,}B\texttt{)}$ 和 $\texttt{max(}A\texttt{,}B\texttt{)}$ 均为合法表达式，这分别表示取左右两边的最大值/最小值。 设 `?` 的个数为 $N$，现在给出一个合法表达式，将每一个问号替换为 $1\sim N$ 中的任意一个数并且每一个数不能使用多次，可以得到多少种不同的答案？ 可怜的 Helena 并不会做，请你帮帮她。

仅一行一个字符串表示给出的合法表达式。

输出一个整数，表示不同答案的个数。

### 样例 1 解释 无论权值如何选择，最后的答案都会是 $\min\{1,2,3,4\}$，也就是 $1$。 ### 样例 2 解释 答案为 $4$ 的方案是： `4=max(4,max(3,min(2,1)))`，答案为 $3$ 的方案是 `3=max(3,max(2,min(1,4)))`，可以证明答案不可能为 $1$ 或 $2$。 ### 数据规模与约定 对于全部数据，$2\le N\le 10^6$。 | Subtask 编号 | 特殊限制 | 得分 | | :----------: | :--------------------------------------------------------------------------: | :--: | | $1$ | $N\le 9$ | $10$ | | $2$ | $N\le 16$ | $13$ | | $3$ | 对于任意 $\texttt{min(}A\texttt{,}B\texttt{)}$ 与 $\texttt{max(}A\texttt{,}B\texttt{)}$，$A$ 和 $B$ 中有一个为 `?`。 | $13$ | | $4$ | $N\le 10^3$ | $30$ | | $5$ | 无特殊限制 | $34$ |