配点 : $800$ 点

問題文

長さ $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$ が成り立つ。

制約

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

入力

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

$N$

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

出力

答えを出力せよ。

3
2 3 1

6

$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$ です。

1
200000

0

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

6
12100 31602 41387 41498 31863 12250

750337372