配点 : $2000$ 点

問題文

$N$ 行 $N$ 列のマスからなる盤面を考えます。アーボックはこの盤面の一部を切り離し、$i = 1, 2, \ldots, N$ のそれぞれについて、左から $i$ 列目は最も下の $h_i$ マスのみが残されています。 そして、残されたマスのうち何マスかにルークを置こうとしています。

ルークはチェスの駒の一種で、$1$ マスを占めます。$1$ 回の移動では、何も置かれていないマスの上を縦か横の一方向に何マスでも動けます。 切り離されたマスの上は通れません。

あるマスについて、そのマスにルークが置かれているか、そのマスに $1$ 回の移動で到達できるルークがあるとき、そのマスは支配下にあるといいます。

残された全マスが支配下に入るように残されたマスのうち何マスかにルークを置く方法の数を $998244353$ で割った余りを求めてください。

制約

• $1 \leq N \leq 400$
• $1 \leq h_i \leq N$
• 入力中のすべての値は整数である。

入力

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

$N$

$h_1$ $h_2$ $...$ $h_N$

出力

残された全マスが支配下に入るように残されたマスのうち何マスかにルークを置く方法の数を $998244353$ で割った余りを出力せよ。

2
2 2

11

$2$ 個以上のルークをどのように置いても条件が満たされ、そのような置き方は $11$ 通りです。

3
2 1 2

17

条件を満たす置き方は次の $17$ 通りです (R がルーク、* が空のマスに対応)。

R *     * R     * *     R R     R R     R R     
**R     R**     R*R     R**     *R*     **R     


R *     R *     * R     * R     * *     R R     
R*R     *RR     RR*     R*R     RRR     RR*     


R R     R R     R *     * R     R R     
R*R     *RR     RRR     RRR     RRR

4
1 2 4 1

201

10
4 7 4 8 4 6 8 2 3 6

263244071