問題文

成分が正の整数である $N$ 次正方行列であって、次の条件を満たすものは何通りありますか。$998244353$ で割った余りを求めてください。

• 各行について広義単調増加
• 各列について広義単調増加
• $i=1,2,\ldots,N$ に対して、$(i,i)$ 成分は $A_i$ である

制約

• $1\le N\le 10^5$
• $1\le A_1\le A_2\le\cdots\le A_N\le 10^9$
• 入力はすべて整数

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

行列の個数を $998244353$ で割った余りを出力してください。

サンプル

3
1 2 3

64

1
5

1

9
101 298 385 414 582 651 775 823 958

789729159