P7444 "EZEC-7" Guess the Permutation

Update: The testdata has been strengthened.

Alice has a permutation $a$ of length $n$, and the numbers in the permutation are $0,1,2,\cdots,n-1$. Bob has nothing to do and wants to guess it, but Alice does not want him to guess it too easily. So she gives Bob some conditions and asks him to guess the permutation. We define $f(l,r)=\text{mex}\{a_l,a_{l+1},\cdots,a_r\}$, where the $\text{mex}$ function means the smallest **non-negative integer** that **does not appear** in a multiset. The conditions Alice gives contain $n$ numbers. The $i$-th number represents the number of pairs $(l,r)$ satisfying $1 \leq l \leq r \leq n$ and $f(l,r)=i-1$. Bob immediately knows that this still cannot determine the whole permutation, so he wants to know how many permutations satisfy the given conditions.

The first line contains a positive integer $n$, representing the length of Alice's permutation. The second line contains $n$ non-negative integers. The $i$-th number $c_i$ represents the number of pairs $(l,r)$ satisfying $l \leq r$ and $f(l,r)=i-1$.

Output the number of permutations satisfying the given conditions modulo $998244353$.

**Sample Explanation** In the first sample, there are two permutations that satisfy the conditions: $\{1,0,2,3\}$ and $\{3,2,0,1\}$. In the second sample, you can find by enumeration that there is no solution that satisfies the requirements. **Constraints** **This problem uses bundled testdata.** * 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): no special constraints. For $100\%$ of the testdata, $1\le n\le5\times10^5$, $c_i \ge 0$, and it is guaranteed that $\sum^{n}_{i=1}c_i=\frac{n(n+1)}{2}-1$. Translated by ChatGPT 5