Second Gap（easy）

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

给定一个整数 $N$ 和一个长度为 $N-1$ 的整数序列 $D=(D_1,D_2,\ldots,D_{N-1})$。

求有多少个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_N)$ 满足：对于每个 $1\le i\le N-1$，后缀 $(P_i,\ldots,P_N)$ 中最大值和次大值所在位置之差的绝对值等于 $D_i$。

答案对 $998244353$ 取模。

输入格式

第一行一个整数 $N$。第二行包含 $N-1$ 个整数 $D_1,\ldots,D_{N-1}$。

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

样例输入 1

3
1 1

样例输出 1

4

样例输入 2

5
1 2 2 1

样例输出 2

0

样例输入 3

15
4 4 4 4 4 4 3 2 2 2 2 2 1 1

样例输出 3

70270200

数据范围

对于全部数据，$2\le N\le3000$，且 $1\le D_i\le N-i$。

来源给出 50% 数据满足 $N\le80$；本次改编在其中增加 $N\le9$ 的真实枚举层，并按 V5 规则将增量分值调整为 20/40/40。新增限制已标记为合成约束。