問題文

広義単調減少する長さ $N$ の数列 $A=(A_{1},A_{2},...,A_{N})$ が与えられます。

空でない長さ $L$ の数列 $B$ に対してその数列のスコア $f(B)$ を以下のように定義します。

• $L=1$ のとき $f(B)=1$
• $L\neq 1$ のとき $\displaystyle f(B)=\prod_{i=2}^{L}\binom{B_{i-1}}{B_{i}}$

$A$ の非空な部分列 $A'$ は $2^{N}-1$ 個ありますが、その全ての $A'$ に対する $f(A')$ の総和を、 $998244353$ で割った余りを求めてください。

ここで $\displaystyle\binom{B_{i-1}}{B_{i}}$ は $B_{i-1}$ 個の区別できるものから ちょうど $B_{i}$ 個のものを選ぶ場合の数、つまり二項係数です。

制約

• $1\leq N \leq 10^{5}$
• $10^{5}\geq A_{1}$
• $A_{i}\geq A_{i+1} \ (2\leq i\leq N)$
• $A_{N}\geq 0$
• 入力は全て整数

入力

$N$
$ A_1 \; A_2 \; ...\;A_N$

出力

答えを出力してください。 最後に改行してください。

サンプル

4
6 4 3 2

469

2
924 167

793971661

12
99740 98332 88628 81080 76561 68844 62493 52907 46058 40949 22847 854

31340893