Conditional Mix

题意翻译

第一行输入一个正整数 $n\le 2\times 10^3$。 第二行输入 $n$ 个正整数 $1\le a_i\le n$。 把 $a_i$ 看成一个一元集 $\{a_i\}$ , 每次可以合并两个交集为空的集合（合并完集合数 $-1$）。可以经过任意次合并。设合并完每个集合的元素个数组成可重集 $S$。求 $S$ 的种类数，对 $998244353$ 取模。

题目描述

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

输入输出格式

输入格式

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 the number of distinct multisets $ M $ modulo $ 998\,244\,353 $ .

输入输出样例

输入样例 #1

6
1 1 2 1 4 3

输出样例 #1

7

输入样例 #2

7
3 5 4 3 7 4 5

输出样例 #2

11

说明

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