题目描述

$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$

输出格式

答えを出力せよ．

题目大意

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$ 由 $0$, $1$ 组成。

在二维平面上坐标为 $(0,0)$ 的一点上有一个棋子。 可以任意重复下面的运算。

• 选定一个整数 $x,y$ ($1 \leq x,y \leq N$) 并将棋子的坐标 $X$ 和 $Y$ 分别增加 $x$ 和 $y$。 但是必须满足以下两个条件。

  • $A_x = 1$。
  • 当操作后棋子的坐标设置为 $(p,q)$ 时，满足 $q \leq p$。

求棋子最终到达坐标 $(N,N)$ 的操作方法数除以 $998244353$。

2
1 1

2

1
0

0

4
1 1 0 1

10

25
1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0

934946952

提示

制約

• $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)$