AT_agc041_f [AGC041F] Histogram Rooks

我们考虑一个有 $N$ 行 $N$ 列的方格网。Arbok 剪掉了网格的一部分，使得对于每个 $i = 1, 2, \ldots, N$，从左往右第 $i$ 列的最底部剩下 $h_i$ 个方格。现在，他想在剩下的某些方格中放置车。 车是一种国际象棋棋子，占据一个格子，可以沿水平方向或垂直方向移动任意步数，只要经过的格子没有被占用。车不能穿过被 Arbok 剪掉的格子。 我们称一个格子被覆盖，当且仅当它本身有车，或者有车能一步移动到该格子。 请你计算有多少种方式可以在剩下的格子中放置车，使得每一个剩下的格子都被覆盖。答案对 $998244353$ 取模。

输入从标准输入读入，格式如下： > $N$ > > $h_1$ $h_2$ $...$ $h_N$

输出一个整数，表示有多少种放置车的方案，使得每一个剩下的格子都被覆盖。答案对 $998244353$ 取模。

### 数据范围 - $1 \leq N \leq 400$ - $1 \leq h_i \leq N$ - 所有输入值均为整数。 ### 样例解释 1 只要至少放两个车的任意方案都可以。这样的方案共有 $11$ 种。 ### 样例解释 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 ``` 由 ChatGPT 4.1 翻译