Master of Array Construction

Time limit4sMemory limit1024 MB

Summary

Count the ways to replace each 0 in an array of length N with a value from 1 to N so that each value x appears at most x times, modulo 998244353.

Problem

An array $A$ of length $N$ consists of integers from $0$ to $N$ .

Jiro wants to replace every element with value $0$ with an integer from $1$ to $N$ . The resulting array must satisfy the following condition.

For each integer $x$ from $1$ to $N$ , the number of times $x$ appears in array $A$ is at most $x$ .

Find the number of arrays Jiro can build that satisfy the condition, modulo $998244353$ . $998244353$ is prime.

The first line contains the length $N$ of array $A$ . ( $1 \le N \le 3000$ )

The second line contains $A_1, A_2, \cdots, A_N$ , separated by spaces. ( $0 \le A_i \le N$ )

Print the number of arrays Jiro can build that satisfy the condition, modulo $998244353$ .