Background

Update: The testdata has been strengthened.

Problem Description

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.

Input Format

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 Format

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

4
4 3 1 1

2

4
4 0 3 2

0

Hint

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