CF1740F.Conditional Mix

Pak Chanek is given an array $a$ of $n$ integers. For each $i$ ($1 \leq i \leq n$), Pak Chanek will write the one-element set ${a_i}$ on a whiteboard.

After that, in one operation, Pak Chanek may do the following:

1. Choose two different sets $S$ and $T$ on the whiteboard such that $S \cap T = \varnothing$ ($S$ and $T$ do not have any common elements).
2. Erase $S$ and $T$ from the whiteboard and write $S \cup T$ (the union of $S$ and $T$) onto the whiteboard.

After performing zero or more operations, Pak Chanek will construct a multiset $M$ containing the sizes of all sets written on the whiteboard. In other words, each element in $M$ corresponds to the size of a set after the operations.

How many distinct$^\dagger$ multisets $M$ can be created by this process? Since the answer may be large, output it modulo $998\,244\,353$.

$^\dagger$ Multisets $B$ and $C$ are different if and only if there exists a value $k$ such that the number of elements with value $k$ in $B$ is different than the number of elements with value $k$ in $C$.

Pak Chanek 被给定一个包含 $n$ 个整数的数组 $a$。对于每个 $i$（$1 \leq i \leq n$），Pak Chanek 将在黑板上写下仅含一个元素的集合 $\{a_i\}$。

此后，每次操作中，Pak Chanek 可执行以下步骤：

1. 在黑板上选择两个互不相交的集合 $S$ 和 $T$（即满足 $S \cap T = \varnothing$）；
2. 将 $S$ 和 $T$ 从黑板上擦除，并将它们的并集 $S \cup T$ 写回黑板。

在执行零次或多次上述操作后，Pak Chanek 将构造一个多重集 $M$，其中包含黑板上所有剩余集合的大小。换言之，$M$ 中的每个元素对应一次操作结束后某个集合的大小。

通过该过程，总共能构造出多少个互不相同$^\dagger$ 的多重集 $M$？由于答案可能很大，请对 $998\,244\,353$ 取模输出。

$^\dagger$ 多重集 $B$ 与 $C$ 被视为不同，当且仅当存在某个值 $k$，使得 $k$ 在 $B$ 中的出现次数与在 $C$ 中的出现次数不同。

The first line contains a single integer $n$ ($1 \le n \le 2000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

第一行包含一个整数 $n$（$1 \le n \le 2000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

Output the number of distinct multisets $M$ modulo $998\,244\,353$.

输出不同的多重集 $M$ 的数量，对 $998\,244\,353$ 取模。

In the first example, the possible multisets $M$ are ${1,1,1,1,1,1}$, ${1,1,1,1,2}$, ${1,1,1,3}$, ${1,1,2,2}$, ${1,1,4}$, ${1,2,3}$, and ${2,2,2}$.

As an example, let's consider a possible sequence of operations.

1. In the beginning, the sets are ${1}$, ${1}$, ${2}$, ${1}$, ${4}$, and ${3}$.
2. Do an operation on sets ${1}$ and ${3}$. Now, the sets are ${1}$, ${1}$, ${2}$, ${4}$, and ${1,3}$.
3. Do an operation on sets ${2}$ and ${4}$. Now, the sets are ${1}$, ${1}$, ${1,3}$, and ${2,4}$.
4. Do an operation on sets ${1,3}$ and ${2,4}$. Now, the sets are ${1}$, ${1}$, and ${1,2,3,4}$.
5. The multiset $M$ that is constructed is ${1,1,4}$.

在第一个例子中，可能的多重集 $M$ 有：${1,1,1,1,1,1}$、${1,1,1,1,2}$、${1,1,1,3}$、${1,1,2,2}$、${1,1,4}$、${1,2,3}$ 和 ${2,2,2}$。

举个例子，我们考虑一种可能的操作序列：

1. 初始时，各集合为 ${1}$、${1}$、${2}$、${1}$、${4}$ 和 ${3}$。
2. 对集合 ${1}$ 和 ${3}$ 执行一次操作。此时各集合变为 ${1}$、${1}$、${2}$、${4}$ 和 ${1,3}$。
3. 对集合 ${2}$ 和 ${4}$ 执行一次操作。此时各集合变为 ${1}$、${1}$、${1,3}$ 和 ${2,4}$。
4. 对集合 ${1,3}$ 和 ${2,4}$ 执行一次操作。此时各集合变为 ${1}$、${1}$ 和 ${1,2,3,4}$。
5. 最终构造出的多重集 $M$ 为 ${1,1,4}$。