条件合并

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定 $n$ 个整数 $a_1,\ldots,a_n$。初始时，白板上写有 $n$ 个单元素集合 $\{a_i\}$。

每次可以选择两个没有公共元素的不同集合 $S,T$，擦除它们并写下 $S\cup T$。执行任意次操作后，把白板上所有集合的大小组成多重集 $M$。

求可能得到多少种不同的多重集 $M$，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示不同多重集的数量对 $998244353$ 取模的结果。

样例输入 1

6
1 1 2 1 4 3

样例输出 1

7

样例输入 2

7
3 5 4 3 7 4 5

样例输出 2

11

数据范围

$1\le n\le2000$，$1\le a_i\le n$。

每个测试点独立计分。