B - Self Checkout Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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.

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:

  1. Set a variable C = 0.
  2. If A contains at least one 1, remove the first occurrence of 1 from A and add 1 to C.
  3. If A is not empty, remove the first element x of A and add x to C.
  4. Append C to the end of T.
  5. If A is empty, terminate the process. Otherwise, return to step 1.

Constraints

  • All input values are integers.
  • 1 \le N \le 10^6
  • 1 \le S_i \le 3

Input

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

N
S_1 S_2 \dots S_N

Output

Output the number of sequences A that satisfy the conditions, modulo 998244353.

Sample Input 1

2
3 2

Sample Output 1

5

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

For example, for A = (2, 1, 1, 1), the process proceeds as follows:

  • Remove the first occurrence of 1 in A, which is A_2 = 1. Now A = (2, 1, 1) and C = 1.
  • Remove the first element of A, which is A_1 = 2. Now A = (1, 1) and C = 3.
  • Append C to the end of T. Now T = (3).
  • Remove the first occurrence of 1 in A, which is A_1 = 1. Now A = (1) and C = 1.
  • Remove the first element of A, which is A_1 = 1. Now A = () and C = 2.
  • Append C to the end of T. Now T = (3, 2).

Sample Input 2

6
3 2 2 3 2 1

Sample Output 2

4

Sample Input 3

5
3 2 1 3 2

Sample Output 3

0

Note that there may be cases where no sequence A produces S, in which case the answer is 0.

配点 : 100 点

問題文

1, 2, 3 からなる長さ N の数列 S が与えられます。1, 2 からなる数列 A であって、以下の問題の答えが S になるようなものの個数を 998244353 で割ったあまりを求めてください。ここで、求める数列 A の個数は有限となることが示せます。

空の数列 T があります。 1, 2 からなる数列 A が与えられます。次の処理を行った後の数列 T を求めてください。

  1. 変数 C を C = 0 として初期化する。
  2. A に 1 が含まれるならば、1 のうち最も先頭に近いものを A から取り除き、C に 1 を加算する。
  3. A が空でないならば、先頭の要素 x を A から取り除き、C に x を加算する。
  4. T の末尾に C を追加する。
  5. A が空ならば処理を終了する。そうでないなら 1. に戻る。

制約

  • 入力はすべて整数
  • 1 \le N \le 10^6
  • 1 \le S_i \le 3

入力

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

N
S_1 S_2 \dots S_N

出力

条件を満たす数列 A の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

2
3 2

出力例 1

5

問題の答えが (3,2) となる数列 A は (1,2,2), (2,1,2), (2,2,1), (2,1,1,1), (1,2,1,1) の 5 通りです。

例えば (2,1,1,1) の場合は、以下のように問題は処理されます。

  • A の 1 のうち最も先頭に近いものである A_2 = 1 を削除する。A = (2,1,1), C = 1 となる。
  • A の先頭の要素である A_1 = 2 を削除する。 A = (1,1), C = 3 となる。
  • C を T の末尾に追加する。 T = (3) となる。
  • A の 1 のうち最も先頭に近いものである A_1 = 1 を削除する。 A = (1), C = 1 となる。
  • A の先頭の要素である A_1 = 1 を削除する。 A = (), C = 2 となる。
  • C を T の末尾に追加する。 T = (3, 2) となる。

入力例 2

6
3 2 2 3 2 1

出力例 2

4

入力例 3

5
3 2 1 3 2

出力例 3

0

問題の答えが S となる数列 A の個数が 0 個の場合もあります。