问题描述

给定$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 \lor b$是逻辑运算符。

约束条件

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

输入

输入通过标准输入给出，格式如下：

N
S_1
...
S_N

输出

打印答案。

样例输入1

2
AND
OR

样例输出1

5

例如，如果$(x_0,x_1,x_2)=(\text{True},\text{False},\text{True})$，则$y_2 = \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}$的五个元组$(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})$

样例输入2

5
OR
OR
OR
OR
OR

样例输出2

63

除了全为$\text{False}$的元组外，所有元组都使得$y_5 = \text{True}$。