← 返回题目列表

AtCoder · toyota2023spring_final_e

E. 东-东北

中文机器翻译题面 查看原题

配点 : 1000 点

問題文

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 后求余数。

制約

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

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

打印答案。


入力例 1

2
1 1

出力例 1

2

作为棋子的移动方法,以下 2 种情况可以考虑。

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

入力例 2

1
0

出力例 2

0

入力例 3

4
1 1 0 1

出力例 3

10

入力例 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