{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $S$ of length $N$, consisting of integers $1$, $2$, and $3$. Determine the number of sequences $A$ consisting of integers $1$ and $2$ such that the sequence $T$ obtained after performing the following procedure matches $S$. Output the answer modulo $998244353$. It can be proven that the number of such sequences $A$ is finite.\n\n> Start with an empty sequence $T$. Given a sequence $A$ consisting of integers $1$ and $2$, perform the following process to obtain the sequence $T$:\n> \n> 1.  Set a variable $C = 0$.\n> 2.  If $A$ contains at least one $1$, remove the first occurrence of $1$ from $A$ and add $1$ to $C$.\n> 3.  If $A$ is not empty, remove the first element $x$ of $A$ and add $x$ to $C$.\n> 4.  Append $C$ to the end of $T$.\n> 5.  If $A$ is empty, terminate the process. Otherwise, return to step 1."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le N \\le 10^6$\n*   $1 \\le S_i \\le 3$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S_1$ $S_2$ $\\dots$ $S_N$"},{"iden":"sample input 1","content":"2\n3 2"},{"iden":"sample output 1","content":"5\n\nThere are $5$ possible sequences $A$ that result in $T = (3, 2)$: $A = (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 1, 1), (1, 2, 1, 1)$.\nFor example, for $A = (2, 1, 1, 1)$, the process proceeds as follows:\n\n*   Remove the first occurrence of $1$ in $A$, which is $A_2 = 1$. Now $A = (2, 1, 1)$ and $C = 1$.\n*   Remove the first element of $A$, which is $A_1 = 2$. Now $A = (1, 1)$ and $C = 3$.\n*   Append $C$ to the end of $T$. Now $T = (3)$.\n*   Remove the first occurrence of $1$ in $A$, which is $A_1 = 1$. Now $A = (1)$ and $C = 1$.\n*   Remove the first element of $A$, which is $A_1 = 1$. Now $A = ()$ and $C = 2$.\n*   Append $C$ to the end of $T$. Now $T = (3, 2)$."},{"iden":"sample input 2","content":"6\n3 2 2 3 2 1"},{"iden":"sample output 2","content":"4"},{"iden":"sample input 3","content":"5\n3 2 1 3 2"},{"iden":"sample output 3","content":"0\n\nNote that there may be cases where no sequence $A$ produces $S$, in which case the answer is $0$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}