题目描述

给定 $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$ $\\vdots$ $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}$。