AT_abc189_d [ABC189D] Logical Expression

给定 $N$ 个字符串 $S_1,\ldots,S_N$，每个字符串为 `AND` 或 `OR`。 请计算有多少组 $N+1$ 个变量 $(x_0,\ldots,x_N)$，每个变量的取值为 $\text{True}$ 或 $\text{False}$，使得按照如下方式计算后，$y_N$ 的值为 $\text{True}$。 - $y_0 = x_0$ - 当 $i \geq 1$ 时，若 $S_i$ 为 `AND`，则 $y_i = y_{i-1} \land x_i$；若 $S_i$ 为 `OR`，则 $y_i = y_{i-1} \lor x_i$ 其中 $a \land b$ 表示 $a$ 与 $b$ 的逻辑与，$a \lor b$ 表示 $a$ 与 $b$ 的逻辑或。

输入以如下格式从标准输入读入： > $N$ > $S_1$ > $\vdots$ > $S_N$

请输出答案。

## 限制条件 - $1 \leq N \leq 60$ - $S_i$ 为 `AND` 或 `OR` ## 样例解释 1 例如，当 $(x_0,x_1,x_2)=(\text{True},\text{False},\text{True})$ 时： - $y_0 = x_0 = \text{True}$ - $y_1 = y_0 \land x_1 = \text{True} \land \text{False} = \text{False}$ - $y_2 = y_1 \lor x_2 = \text{False} \lor \text{True} = \text{True}$ 因此 $y_2$ 的值为 $\text{True}$。 使 $y_2$ 为 $\text{True}$ 的 $(x_0,x_1,x_2)$ 的组合共有： - $(\text{True},\text{True},\text{True})$ - $(\text{True},\text{True},\text{False})$ - $(\text{True},\text{False},\text{True})$ - $(\text{False},\text{True},\text{True})$ - $(\text{False},\text{False},\text{True})$ 共 $5$ 种。 ## 样例解释 2 除了所有变量均为 $\text{False}$ 的情况外，其余 $2^6-1$ 种组合都能使 $y_5$ 为 $\text{True}$。 由 ChatGPT 4.1 翻译