9698: ABC189 —— D - Logical expression
[Creator : ]
Description
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.
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.
Input
Input is given from Standard Input in the following format:
```
$N$
$S_1$
$\vdots$
$S_N$
```
```
$N$
$S_1$
$\vdots$
$S_N$
```
Output
Print the answer.
Constraints
- $1 \leq N \leq 60$
- $S_i$ is `AND` or `OR`.
- $S_i$ is `AND` or `OR`.
Sample 1 Input
2
AND
OR
Sample 1 Output
5
For example, if $(x_0,x_1,x_2)$=(True,False,True), we have $y_2$=True, as follows:
- $y_0=x_0$=True
- $y_1=y_0∧x_1$=True∧False=False
- $y_2=y_1∨x_2$=False∨True=True
All of the five tuples $(x_0,x_1,x_2)$ resulting in $y_2$=True are shown below:
- (True,True,True)
- (True,True,False)
- (True,False,True)
- (False,True,True)
- (False,False,True)
Sample 2 Input
5
OR
OR
OR
OR
OR
Sample 2 Output
63
All tuples except the one filled entirely with FalseFalse result in $y_5$=True.