题目描述

長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

$1$ 以上 $N$ 以下の整数からなる整数列 $B$ のうち、以下の条件を全て満たすものの個数を $998244353$ で割ったあまりを出力してください。

• $1\ \le\ i\ \le\ N$ を満たす整数 $i$ に対し、$B$ の中に $i$ はちょうど $A_i$ 個存在する。
• $1\ \le\ i\ \le\ |B|-1$ を満たす整数 $i$ に対し、$|B_i\ -\ B_{i+1}|=1$ が成り立つ。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

答えを出力せよ。

题目大意

给定长为 $N$ 的序列 $A_i$ ，求满足要求的序列 $B$ 的数量：元素为 $[1, N]$ 且 $i$ 刚好出现 $A_i$ 次，$|B_i - B_{i - 1}| = 1$。

Translate by

3
2 3 1

6

1
200000

0

6
12100 31602 41387 41498 31863 12250

750337372

提示

制約

• $1\ \le\ N\ \le\ 2\ \times\ 10^5$
• $1\ \le\ A_i\ \le\ 2\ \times\ 10^5$
• 入力はすべて整数である。

Sample Explanation 1

$B$ としてあり得るものは、以下の $6$ 通りがあります。 - $(1,2,1,2,3,2)$ - $(1,2,3,2,1,2)$ - $(2,1,2,1,2,3)$ - $(2,1,2,3,2,1)$ - $(2,3,2,1,2,1)$ - $(3,2,1,2,1,2)$ よって、解は $6$ です。

Sample Explanation 2

条件を満たす $B$ が存在しないこともあります。