AT_ttpc2024_1_b Self Checkout

$ 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. に戻る。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \dots $ $ S_N $

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

### Sample Explanation 1 問題の答えが $ (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) $ となる。 ### Sample Explanation 3 問題の答えが $ S $ となる数列 $ A $ の個数が $ 0 $ 個の場合もあります。 ### Constraints - 入力はすべて整数 - $ 1 \le N \le 10^6 $ - $ 1 \le S_i \le 3 $