题目描述

题目译自 CEOI 2022 Day1 T2「Homework」

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

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

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

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

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

输入格式

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

输出格式

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

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

1

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

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

2

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

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

3

数据范围与提示

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