101893: [AtCoder]ABC189 D - Logical Expression

Problem Statement

Given are $N$ strings $S_1,\ldots,S_N$, each of which is AND or OR.

Find the number of tuples of $N+1$ variables $(x_0,\ldots,x_N)$, where each element is $\text{True}$ or $\text{False}$, such that the following computation results in $y_N$ being $\text{True}$:

• $y_0=x_0$;
• for $i\geq 1$, $y_i=y_{i-1} \land x_i$ if $S_i$ is AND, and $y_i=y_{i-1} \lor x_i$ if $S_i$ is OR.

Here, $a \land b$ and $a \lor b$ are logical operators.

Constraints

• $1 \leq N \leq 60$
• $S_i$ is AND or OR.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

2
AND
OR

Sample Output 1

5

For example, if $(x_0,x_1,x_2)=(\text{True},\text{False},\text{True})$, we have $y_2 = \text{True}$, as follows:

• $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}$

All of the five tuples $(x_0,x_1,x_2)$ resulting in $y_2 = \text{True}$ are shown below:

• $(\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})$

Sample Input 2

5
OR
OR
OR
OR
OR

Sample Output 2

63

All tuples except the one filled entirely with $\text{False}$ result in $y_5 = \text{True}$.