题目背景

Update：数据已经经过加强。

题目描述

Alice 手上有一个长度为 $n$ 的排列 $a$，排列中的数为 $0,1,2,\cdots,n-1$。

Bob 闲来无事，想去猜它。但 Alice 不想让他轻易猜到。

于是他抛给了 Bob 一些条件，让他来猜这个排列。

我们定义 $f(l,r)=\text{mex}\{a_l,a_{l+1},\cdots,a_r\}$，其中 $\text{mex}$ 函数代表一个可重集中没有出现过的最小非负整数。

而 Alice 说出的条件包含 $n$ 个数，第 $i$ 个数代表着满足 $1 \leq l \leq r \leq n$ 且 $f(l,r)=i-1$ 的二元组 $(l,r)$ 的个数。

Bob 一下就知道这并不能确认整个排列了，因此他想知道符合已有条件的排列数量。

输入格式

第一行，一个正整数 $n$，代表 Alice 手中排列的长度。

第二行，$n$ 个非负整数，第 $i$ 个数 $c_i$ 代表着满足 $l \leq r$ 且 $f(l,r)=i-1$ 的二元组 $(l,r)$ 的个数。

输出格式

输出符合已有条件的排列数量对 $998244353$ 取模的值。

4
4 3 1 1

2

4
4 0 3 2

0

提示

【样例解释】

第一个样例中存在两个满足条件的排列，分别为：

$\{1,0,2,3\}$ 和 $\{3,2,0,1\}$ 。

第二个样例可以通过枚举发现没有符合题意的解。

【数据范围】

本题采用捆绑测试。

• Subtask 1（4 points）：$n\leq 8$。
• Subtask 2（8 points）：$n\leq 20$。
• Subtask 3（16 points）：$n\leq 100$。
• Subtask 4（32 points）：$n\leq 2\times 10^3$。
• Subtask 5（20 points）：$n\leq 10^5$。
• Subtask 6（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$c_i \ge 0$，保证 $\sum^{n}_{i=1}c_i=\frac{n(n+1)}{2}-1$。