{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq A_i \\leq 1$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"6\n1 1 1 1 1 0"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"10\n1 1 1 1 1 0 1 1 1 0"},{"iden":"sample output 2","content":"9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}