题目描述

我们考虑一个有 $N$ 行 $N$ 列的方格网。Arbok 剪掉了网格的一部分，使得对于每个 $i = 1, 2, \ldots, N$，从左往右第 $i$ 列的最底部剩下 $h_i$ 个方格。现在，他想在剩下的某些方格中放置车。

车是一种国际象棋棋子，占据一个格子，可以沿水平方向或垂直方向移动任意步数，只要经过的格子没有被占用。车不能穿过被 Arbok 剪掉的格子。

我们称一个格子被覆盖，当且仅当它本身有车，或者有车能一步移动到该格子。

请你计算有多少种方式可以在剩下的格子中放置车，使得每一个剩下的格子都被覆盖。答案对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$

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

输出格式

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

样例 1

输入

2
2 2

输出

11

样例 2

输入

3
2 1 2

输出

17

样例 3

输入

4
1 2 4 1

输出

201

样例 4

输入

10
4 7 4 8 4 6 8 2 3 6

输出

263244071

说明/提示

数据范围

• $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 翻译