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$.

Input

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$).

Output

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

Note

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\}$.