逻辑表达式

题目描述

给定 $N$ 个字符串 $S_1,\ldots,S_N$。每个字符串都是 AND 或 OR。

求值为 $\text{True}$ 或 $\text{False}$ 的 $N+1$ 个变量的组 $(x_0,\ldots,x_N)$ 中，按以下方式计算时能使 $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$ 的逻辑与（AND），$a \lor b$ 表示 $a$ 与 $b$ 的逻辑或（OR）。

输入格式

输入按以下格式从标准输入给出：

$N$
$S_1$
$\vdots$
$S_N$

输出格式

输出答案。

样例

2
AND
OR

5

例如，当 $(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$ 种，即全部。

5
OR
OR
OR
OR
OR

63

除去全部为 $\text{False}$ 的情况，共 $2^6-1$ 种情况下 $y_5$ 为 $\text{True}$。

数据范围

• $1 \leq N \leq 60$
• $S_i$ 是 AND 或 OR