A - Reversi 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

N 個のマスからなるマス目があります。マスには 1 から N の番号が付いています。

始め、マス i(1 \le i \le N) には i \bmod 2 が書かれています。あなたは以下の操作を任意の回数(0 回でもよい)行うことができます。

  • 以下の条件を満たすマス l,r(l+1 < r) を選び、マス l+1,l+2,\dots,r-1 に書かれている整数をマス l に書かれている整数に書き換える。
    • マス l に書かれている整数とマス r に書かれている整数は等しい。
    • マス i(l < i < r) に書かれている整数とマス l に書かれている整数は異なる。

最終的にマス i(1 \le i \le N) に書かれている整数が A_i になるような操作列の個数を 998244353 で割ったあまりを求めてください。

ただし 2 個の操作列が異なるとは、操作列の長さが異なるか、操作列の長さ以下の正整数 t が存在して t 回目の操作で選んだ (l,r) が異なる場合、かつその時に限り言うものとします。

制約

  • 1 \le N \le 2 \times 10^5
  • 0 \le A_i \le 1

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

6
1 1 1 1 1 0

出力例 1

3

各マス i(1 \le i \le N) に書かれている整数を A_i にするためには、例えば以下のように操作を行えばよいです。(ここで、マス目の状態を数列 X = (X_1, X_2, \dots, X_N) のように表します。)

  • はじめ、X = (1, 0, 1, 0, 1, 0) である。
  • マス 2, 4 を選ぶ。X = (1, 0, 0, 0, 1, 0) となる。
  • マス 1, 5 を選ぶ。X = (1, 1, 1, 1, 1, 0) となる。

上記以外にマス i に書かれている整数が A_i になるような操作列の個数は 2 個あるため、答えは 3 です。


入力例 2

10
1 1 1 1 1 0 1 1 1 0

出力例 2

9

Score : 400 points

Problem Statement

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, possibly zero:

  • 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.
    • The integer written in cell l is equal to the integer written in cell r.
    • The integer written in cell i (l < i < r) is different from the integer written in cell l.

Find 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.

Two 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.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 1

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer.


Sample Input 1

6
1 1 1 1 1 0

Sample Output 1

3

To 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).)

  • Initially, X = (1, 0, 1, 0, 1, 0).
  • Choose cells 2 and 4. X becomes (1, 0, 0, 0, 1, 0).
  • Choose cells 1 and 5. X becomes (1, 1, 1, 1, 1, 0).

Besides 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.


Sample Input 2

10
1 1 1 1 1 0 1 1 1 0

Sample Output 2

9