题目描述

给定一个由 $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$。但必须满足以下两个条件：
  • $A_x=1$。
  • 操作后棋子的坐标为 $(p,q)$ 时，需满足 $q \leq p$。

请你求出，使得棋子最终能够到达坐标 $(N,N)$ 的操作方法有多少种。答案对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2
1 1

输出 #1

2

输入输出样例 #2

输入 #2

1
0

输出 #2

0

输入输出样例 #3

输入 #3

4
1 1 0 1

输出 #3

10

输入输出样例 #4

输入 #4

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

输出 #4

934946952

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $A_i \in \{0,1\}$

样例解释 1

棋子的移动方式有以下 $2$ 种：

• $(0,0) \rightarrow (1,1) \rightarrow (2,2)$
• $(0,0) \rightarrow (2,2)$