AT_toyota2023spring_final_e East-Northeast

[problemUrl]: https://atcoder.jp/contests/toyota2023spring-final/tasks/toyota2023spring_final_e $ 0 $, $ 1 $ からなる長さ $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます． 今，二次元平面上の座標 $ (0,0) $ の点に駒があります． あなたはこれから，以下の操作を好きな回数繰り返します． - 整数 $ x,y $ ($ 1\ \leq\ x,y\ \leq\ N $) を選び，駒の $ X $, $ Y $ 座標をそれぞれ $ x $, $ y $ ずつ増やす． ただしここで，以下の $ 2 $ つの条件を満たす必要がある． - $ A_x=1 $ が成立． - 操作後の駒の座標を $ (p,q) $ とおくとき，$ q\ \leq\ p $ が成立． 最終的に駒が座標 $ (N,N) $ へと至るような操作方法が何通りあるかを $ 998244353 $ で割ったあまりを求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ A_i\ \in\ \{0,1\} $ ### Sample Explanation 1 駒の移動方法として，以下の $ 2 $ 通りが考えられます． - $ (0,0)\ \rightarrow\ (1,1)\ \rightarrow\ (2,2) $ - $ (0,0)\ \rightarrow\ (2,2) $