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.