D - Logical Expression /

### 問題文

N 個の文字列 S_1,\ldots,S_N が与えられます。各文字列は AND または OR です。

• y_0=x_0
• i\geq 1 のとき、S_iAND なら y_i=y_{i-1} \land x_iS_iOR なら y_i=y_{i-1} \lor x_i

a \land bab の論理積を表し、a \lor bab の論理和を表します。

### 制約

• 1 \leq N \leq 60
• S_iAND または OR

### 入力

N
S_1
\vdots
S_N


### 入力例 1

2
AND
OR


### 出力例 1

5


• 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} になります。

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})

5 通りで全てです。

### 入力例 2

5
OR
OR
OR
OR
OR


### 出力例 2

63


Score : 400 points

### 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


### 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}.