{"problem":{"name":"Logical Expression","description":{"content":"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 tha","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc189_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 \\leq N \\leq 60$\n*   $S_i$ is `AND` or `OR`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc189_d","tags":[],"sample_group":[["2\nAND\nOR","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})$"],["5\nOR\nOR\nOR\nOR\nOR","63\n\nAll tuples except the one filled entirely with $\\text{False}$ result in $y_5 = \\text{True}$."]],"created_at":"2026-03-03 11:01:14"}}