問題文

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

出力

答えを出力せよ。

入力例 1

3
2 3 1

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

入力例 2

1
200000

出力例 2

0

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

入力例 3

6
12100 31602 41387 41498 31863 12250

出力例 3

750337372