F. Conditional Mixtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputPak 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:   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).  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.InputThe 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).OutputOutput the number of distinct multisets M modulo 998\,244\,353.ExamplesInput
6
1 1 2 1 4 3
Output
7
Input
7
3 5 4 3 7 4 5
Output
11
NoteIn 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.   In the beginning, the sets are \{1\}, \{1\}, \{2\}, \{1\}, \{4\}, and \{3\}.  Do an operation on sets \{1\} and \{3\}. Now, the sets are \{1\}, \{1\}, \{2\}, \{4\}, and \{1,3\}.  Do an operation on sets \{2\} and \{4\}. Now, the sets are \{1\}, \{1\}, \{1,3\}, and \{2,4\}.  Do an operation on sets \{1,3\} and \{2,4\}. Now, the sets are \{1\}, \{1\}, and \{1,2,3,4\}.  The multiset M that is constructed is \{1,1,4\}. 
6
1 1 2 1 4 3

7 
['combinatorics', 'dp', 'math', '*2600']