[AGC041F] Histogram Rooks

### 题目描述 让我们考虑一个 $N$ 行 $N$ 列的正方形棋盘。Arbok切除了棋盘的某些部分使得对于每一个 $i=1,2,3,\ldots ,N$；在第 $i$ 列中只有自最底部往上数 $h_i$ 个格子仍存在于棋盘之中。现在，他想把棋子放入到剩余的棋盘中。 `車`是一种棋子，占据一个方格。如果一个方格所在的同一行或同一列中有一个`車`而且方格与`車`之间没有已被切除的格子，那么这个方格就被`車`所覆盖。特别的，若方格上就是`車`，那么该方格也被`車`覆盖 请找出所有可以使剩余的棋盘的全部方格均被`車`覆盖的棋子放置方案数。答案可能很大，请对 $998244353$取模。 ### 数据范围与限制 - $1 \le N \le 400$ - $1 \le h_i \le N$ - 所有的输入数据均为整数。 ### 样例1解释 任何至少放置两个`車`的方案均为合法方案，这种方案共有11种。 ### 样例2解释 下面列出的17种放置方案属于合法方案（'R'代表'車'，'*'代表这个方格是空的）： ```explain 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 ```

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

入力は以下の形式で標準入力から与えられる。 > $ N $ $ h_1 $ $ h_2 $ $ ... $ $ h_N $

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

2
2 2

11

3
2 1 2

17

4
1 2 4 1

201

10
4 7 4 8 4 6 8 2 3 6

263244071

### 制約 - $ 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 ```