题目描述

小 S 来到了一片地下矿区。矿区可以看作由 $N$ 个竖井和 $N$ 层矿道组成，竖井从左到右编号为 $1,2,\ldots,N$，矿层从下到上编号为 $1,2,\ldots,N$。

由于部分矿道已经塌陷，第 $i$ 个竖井中只有最下面的 $a_i$ 个位置仍然可以使用，其余位置均不可进入。也就是说，位置 $(x,i)$ 存在当且仅当：

现在，小 S 可以在若干个仍然存在的位置中安装信标。每个信标可以沿着所在竖井向上或向下发出信号，也可以沿着所在矿层向左或向右发出信号。信号只能经过仍然存在的位置，不能穿过已经塌陷的位置；信号在传播过程中遇到另一个信标时会被阻挡，不能继续向前传播。

对于一个仍然存在的位置，如果该位置本身安装了信标，或者存在某个信标使得它的信号可以沿同一个竖井或同一个矿层直接传播到该位置，则称这个位置被监测到。

请计算一共有多少种安装信标的方案，使得所有仍然存在的位置都被监测到。答案对 $998244353$ 取模。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $a_1,a_2,\ldots,a_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\le N\le 400$，$1\le a_i\le N$。