{"raw_statement":[{"iden":"problem statement","content":"Given are $N$ strings $S_1,\\ldots,S_N$, each of which is `AND` or `OR`.\nFind 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}$:\n\n*   $y_0=x_0$;\n*   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`.\n\nHere, $a \\land b$ and $a \\lor b$ are logical operators."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 60$\n*   $S_i$ is `AND` or `OR`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"2\nAND\nOR"},{"iden":"sample output 1","content":"5\n\nFor example, if $(x_0,x_1,x_2)=(\\text{True},\\text{False},\\text{True})$, we have $y_2 = \\text{True}$, as follows:\n\n*   $y_0=x_0=\\text{True}$\n*   $y_1=y_0 \\land x_1 = \\text{True} \\land \\text{False}=\\text{False}$\n*   $y_2=y_1 \\lor x_2 = \\text{False} \\lor \\text{True}=\\text{True}$\n\nAll of the five tuples $(x_0,x_1,x_2)$ resulting in $y_2 = \\text{True}$ are shown below:\n\n*   $(\\text{True},\\text{True},\\text{True})$\n*   $(\\text{True},\\text{True},\\text{False})$\n*   $(\\text{True},\\text{False},\\text{True})$\n*   $(\\text{False},\\text{True},\\text{True})$\n*   $(\\text{False},\\text{False},\\text{True})$"},{"iden":"sample input 2","content":"5\nOR\nOR\nOR\nOR\nOR"},{"iden":"sample output 2","content":"63\n\nAll tuples except the one filled entirely with $\\text{False}$ result in $y_5 = \\text{True}$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}