{"problem":{"name":"Reversi 2","description":{"content":"There is a grid consisting of $N$ cells numbered $1$ to $N$. Initially, cell $i$ $(1 \\le i \\le N)$ has an integer $i \\bmod 2$ written in it. You can perform the following operation any number of times","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc189_a"},"statements":[{"statement_type":"Markdown","content":"There is a grid consisting of $N$ cells numbered $1$ to $N$.\nInitially, cell $i$ $(1 \\le i \\le N)$ has an integer $i \\bmod 2$ written in it. You can perform the following operation any number of times, possibly zero:\n\n*   Choose cells $l$ and $r$ ($l+1 < r$) that satisfy the following conditions, and replace each of the integers written in cells $l+1, l+2, \\dots, r-1$ with the integer written in cell $l$.\n    *   The integer written in cell $l$ is equal to the integer written in cell $r$.\n    *   The integer written in cell $i$ $(l < i < r)$ is different from the integer written in cell $l$.\n\nFind the number, modulo $998244353$, of sequences of operations that result in the integers written in cell $i$ ($1 \\leq i \\leq N$) being $A_i$.\nTwo sequences of operations are considered different if and only if their lengths are different or there exists a positive integer $t$ not exceeding the length of the sequences such that the $(l, r)$ chosen in the $t$\\-th operations differ.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq A_i \\leq 1$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc189_a","tags":[],"sample_group":[["6\n1 1 1 1 1 0","3\n\nTo make the integers written in each cell $i$ equal to $A_i$, for example, you can perform the following operations. (Here, we represent the state of the grid as a sequence $X = (X_1, X_2, \\dots, X_N)$.)\n\n*   Initially, $X = (1, 0, 1, 0, 1, 0)$.\n*   Choose cells $2$ and $4$. $X$ becomes $(1, 0, 0, 0, 1, 0)$.\n*   Choose cells $1$ and $5$. $X$ becomes $(1, 1, 1, 1, 1, 0)$.\n\nBesides the above, there are two other sequences of operations that result in the integers written in cell $i$ being $A_i$, so the answer is $3$."],["10\n1 1 1 1 1 0 1 1 1 0","9"]],"created_at":"2026-03-03 11:01:14"}}