AT_agc041_f [AGC041F] Histogram Rooks

[problemUrl]: https://atcoder.jp/contests/agc041/tasks/agc041_f $ N $ 行 $ N $ 列のマスからなる盤面を考えます。アーボックはこの盤面の一部を切り離し、$ i\ =\ 1,\ 2,\ \ldots,\ N $ のそれぞれについて、左から $ i $ 列目は最も下の $ h_i $ マスのみが残されています。 そして、残されたマスのうち何マスかにルークを置こうとしています。 ルークはチェスの駒の一種で、$ 1 $ マスを占めます。$ 1 $ 回の移動では、何も置かれていないマスの上を縦か横の一方向に何マスでも動けます。 切り離されたマスの上は通れません。 あるマスについて、そのマスにルークが置かれているか、そのマスに $ 1 $ 回の移動で到達できるルークがあるとき、そのマスは支配下にあるといいます。 残された全マスが支配下に入るように残されたマスのうち何マスかにルークを置く方法の数を $ 998244353 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 400 $ - $ 1\ \leq\ h_i\ \leq\ N $ - 入力中のすべての値は整数である。 ### Sample Explanation 1 $ 2 $ 個以上のルークをどのように置いても条件が満たされ、そのような置き方は $ 11 $ 通りです。 ### Sample Explanation 2 条件を満たす置き方は次の $ 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 ```