题目描述

题目译自 CEOI 2022 Day1 T2「Homework」

这是 Helena 的数学作业中的一道题：

我们定义合法表达式如下：

• ? 是合法表达式，这表示一个未知数。
• 如果 $A,B$ 均为合法表达式，那么 $\text{min}(A,B)$ 和 $\text{max}(A,B)$ 均为合法表达式，这分别表示取左右两边的最大值/最小值。

设 ? 的个数为 $N$，现在给出一个合法表达式，将每一个问号替换为 $1 \sim N$ 中的任意一个数并且每一个数不能使用多次，可以得到多少种不同的答案？

可怜的 Helena 并不会做，请你帮帮她。

输入格式

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

输出格式

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

样例 1

输入

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

输出

1

解释
无论权值如何选择，最后的答案都会是 $\min\{1,2,3,4\}$，也就是 $1$。

样例 2

输入

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

输出

2

解释
答案为 $4$ 的方案是： $4=\text{max}(4,\text{max}(3,\text{min}(2,1)))$，答案为 $3$ 的方案是 $3=\text{max}(3,\text{max}(2,\text{min}(1,4)))$，可以证明答案不可能为 $1$ 或 $2$。

样例 3

输入

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

输出

3

数据范围与提示

对于全部数据，$2 \le N \le 10^6$。

Subtask 编号	特殊限制	得分
1	$N \le 9$	10
2	$N \le 16$	13
3	对于任意 $\text{min}(A,B)$ 与 $\text{max}(A,B)$，$A$ 和 $B$ 中有一个为 ?
4	$N \le 10^3$	30
5	无特殊限制	34