{"problem":{"name":"Self Checkout","description":{"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_b"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\le N \\le 10^6$\n*   $1 \\le S_i \\le 3$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S_1$ $S_2$ $\\dots$ $S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_b","tags":[],"sample_group":[["2\n3 2","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)$."],["6\n3 2 2 3 2 1","4"],["5\n3 2 1 3 2","0\n\nNote that there may be cases where no sequence $A$ produces $S$, in which case the answer is $0$."]],"created_at":"2026-03-03 11:01:14"}}