Patient Stack

题目描述

You start with an empty stack and push the elements $1, 2, \ldots, n$ in this exact increasing order, each exactly once. Between the pushes, you may interleave any number of pop operations, each removing the current top of the stack.

A sequence of operations is complete if, in the end, every element has been pushed and the stack is empty (so it contains exactly $n$ pushes and $n$ pops, and at no moment have there been more pops than pushes).

Each element $i$ has a patience $a_i$: after element $i$ is pushed, at least $a_i$ more push operations must occur before $i$ is allowed to be popped. Since the elements are pushed in increasing order, this is the same as saying that element $i$ may be popped only after element $i + a_i$ has been pushed (that is, once all of $i+1, i+2, \ldots, i+a_i$ are in). In particular, if $i + a_i \gt n$, there are not enough later elements, so element $i$ can never be popped.

Count the complete operation sequences that satisfy the patience constraint of every element, modulo $998244353$.

输入格式

The first line contains a single integer $n$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$.

$1 \le n \le 5000$, $0 \le a_i \le n$.

输出格式

Print a single integer — the number of valid complete operation sequences, modulo $998244353$.

Note that if some element $i$ satisfies $a_i \gt n - i$, then fewer than $a_i$ pushes remain after it, so it can never be popped in time, and the answer is $0$.

样例输入 #1

3
0 0 0

样例输出 #1

5

样例输入 #2

4
2 0 0 0

样例输出 #2

7

样例输入 #3

2
2 0

样例输出 #3

0