問題文

無限に広がる $2$ 次元グリッドがあります。それぞれのマスは白または黒で塗られています。具体的には、各 $i = 1, 2, \ldots, N$ について、マス $(i, 1), (i, 2), \ldots, (i, A_i)$ が白く塗られており、それ以外のマスはすべて黒く塗られています。

はじめ、まぐすた君はマス $(1, 1)$ にいます。まぐすた君は次の行動を繰り返すことで、マス $(N, 1)$ に行こうとしています。

• 今いるマスを $(i, j)$ とする。マス $(i, j)$ を黒く塗る。その後、マス $(i + 1, j), (i, j + 1), (i, j - 1)$ のうちで白く塗られているマスを $1$ つ選び、そのマスに移動する。

マス $(N, 1)$ に行く方法の数を $998244353$ で割ったあまりを求めてください。

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

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

出力

マス $(N, 1)$ に行く方法の数を $998244353$ で割ったあまりを出力してください。最後に改行してください。

サンプル

3
1 3 2

2

5
427547210 327546386 963298277 230265126 293165710

538454432